- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我正在尝试解决编程竞赛问题。我在这个部门几乎是个菜鸟(我想我有很多东西要学)。我试图解决这个问题,其中包括读取二维数组 (n x m
) 并找出其中的 Blob 。 Blob 由连续发光的像素(用 #
表示)形成。不亮像素(由 .
表示)。我试图通过使用递归方法 Blob::form()
来查找 blob。示例输入可能如下所示
1
6 6
#...#.
.#.#.#
##..#.
......
.#.#.#
#...#.
我很快想到了解决方案。而且并不多。但一如既往,它在最坏的情况下失败 n = m = 1000
并且所有字符都是 #
。这个的 1000 x 1000 版本:
1
3 3
###
###
###
我假设的问题是堆栈溢出。我发现程序在形成 blob 时崩溃了。
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
int pat[1000][1000],n,m;
char a[1000][1000];
struct point
{
int x,y;
};
bool inBounds(point p)
{
if(p.x < n && p.x >=0 && p.y < m && p.y >= 0) return true;
else return false;
}
bool isAblob(int i,int j)
{
point p[8];
p[0].x = i-1; p[0].y = j;
p[1].x = i+1; p[1].y = j;
p[2].x = i+1; p[2].y = j+1;
p[3].x = i-1; p[3].y = j-1;
p[4].x = i-1; p[4].y = j+1;
p[5].x = i+1; p[5].y = j-1;
p[6].x = i; p[6].y = j-1;
p[7].x = i; p[7].y = j+1;
for(int k=0;k<8;k++)
{
if(inBounds(p[k]))
{
if(a[p[k].x][p[k].y] == '#') return true;
}
}
return false;
}
class Blob
{
public:
long long int pow;
Blob(int i, int j)
{
this->pow = 0;
point po;
po.x=i;
po.y=j;
this->form(&po);
}
int getPow()
{
return this->pow;
}
void form ( point *p)
{
if(inBounds(*p))
{
if(a[p->x][p->y] == '#' && !pat[p->x][p->y])
{
a[p->x][p->y] = 1;
this->pow++;
point *e = new point;
e->x = p->x-1; e->y = p->y;if(pat[e->x][e->y] == 0)form(e);
e->x = p->x+1; e->y = p->y;if(pat[e->x][e->y] == 0)form(e);
e->x = p->x+1; e->y = p->y+1;if(pat[e->x][e->y] == 0)form(e);
e->x = p->x-1; e->y = p->y-1;if(pat[e->x][e->y] == 0)form(e);
e->x = p->x-1; e->y = p->y+1;if(pat[e->x][e->y] == 0)form(e);
e->x = p->x+1; e->y = p->y-1;if(pat[e->x][e->y] == 0)form(e);
e->x = p->x; e->y = p->y-1;if(pat[e->x][e->y] == 0)form(e);
e->x = p->x; e->y = p->y+1;
if(pat[e->x][e->y] == 0)form(e);
}
}
return;
}
};
int main()
{
int t;
cin >> t;
for (int q = 0; q < t; q++)
{
cin >> n >> m;
int bnum = 0;
Blob *b[(n*m)/2];
vector <int> pows;
cin.get();
for(int i=0;i<n;i++)
{
for(int j = 0; j<m;j++)
{
a[i][j] = cin.get();
pat[i][j] = 0;
}
cin.get();
}
for(int i=0;i<n;i++)
{
for(int j = 0; j<m;j++)
{
if(a[i][j] == '#' && pat[i][j] == 0)
{
if(isAblob(i,j))
{
bnum++;
b[bnum] = new Blob(i,j);
pows.push_back(b[bnum]->getPow());
}
else continue;
}
else continue;
}
}
sort(pows.begin(),pows.end());
cout << endl << bnum;
for(int i=1;i<=bnum;i++)
{
if(i==1) cout << endl;
if(i!=1) cout << " ";
cout << pows[i-1];
}
}
}
我确定我的代码有问题且效率低下。我想知道是否有人可以告诉我将来如何避免这些问题。更好的实现也很有帮助。但我正在寻找的是避免将来发生堆栈溢出的技巧。
最佳答案
在不改变程序逻辑的情况下避免递归的一种简单方法是直接使用堆栈数据结构,而不是通过调用堆栈。
这是使用 std::stack 的 Blob 类的修改版本在你的表单函数中:
class Blob
{
public:
long long int pow;
Blob(int i, int j)
{
this->pow = 0;
point po;
po.x=i;
po.y=j;
this->form(po);
}
int getPow()
{
return this->pow;
}
void form (point p)
{
std::stack<point> s;
s.push(p);
while (!s.empty())
{
p=s.top();
s.pop();
if (!inBounds(p))
continue;
if(a[p.x][p.y] == '#' && !pat[p.x][p.y])
{
a[p.x][p.y] = 1;
this->pow++;
point e;
e.x = p.x-1; e.y = p.y; if(pat[e.x][e.y] == 0)s.push(e);
e.x = p.x+1; e.y = p.y; if(pat[e.x][e.y] == 0)s.push(e);
e.x = p.x+1; e.y = p.y+1; if(pat[e.x][e.y] == 0)s.push(e);
e.x = p.x-1; e.y = p.y-1; if(pat[e.x][e.y] == 0)s.push(e);
e.x = p.x-1; e.y = p.y+1; if(pat[e.x][e.y] == 0)s.push(e);
e.x = p.x+1; e.y = p.y-1; if(pat[e.x][e.y] == 0)s.push(e);
e.x = p.x; e.y = p.y-1; if(pat[e.x][e.y] == 0)s.push(e);
e.x = p.x; e.y = p.y+1; if(pat[e.x][e.y] == 0)s.push(e);
}
}
}
};
请注意,这也会修复您的内存泄漏。
一般来说,您要解决的问题似乎是寻找具有方形邻域的“连通分量”。通常,您会使用 disjoint-set data-structure解决这个问题,不需要堆栈或递归。有了它,您只需扫描一次该字段,就可以得到所有连接组件的大小,而不仅仅是检查 blob 的组件。
关于c++ - 如何避免此代码中的堆栈溢出,(递归函数),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32252736/
在本教程中,您将借助示例了解 JavaScript 中的递归。 递归是一个调用自身的过程。调用自身的函数称为递归函数。 递归函数的语法是: function recurse() {
我的类(class) MyClass 中有这段代码: public new MyClass this[int index] { get {
我目前有一个非常大的网站,大小约为 5GB,包含 60,000 个文件。当前主机在帮助我将站点转移到新主机方面并没有做太多事情,我想的是在我的新主机上制作一个简单的脚本以 FTP 到旧主机并下载整个
以下是我对 AP 计算机科学问题的改编。书上说应该打印00100123我认为它应该打印 0010012但下面的代码实际上打印了 3132123 这是怎么回事?而且它似乎没有任何停止条件?! publi
fun fact(x: Int): Int{ tailrec fun factTail(y: Int, z: Int): Int{ if (y == 0) return z
我正在尝试用c语言递归地创建线性链表,但继续坚持下去,代码无法正常工作,并出现错误“链接器工具错误 LNK2019”。可悲的是我不明白发生了什么事。这是我的代码。 感谢您提前提供的大力帮助。 #inc
我正在练习递归。从概念上讲,我理解这应该如何工作(见下文),但我的代码不起作用。 请告诉我我做错了什么。并请解释您的代码的每个步骤及其工作原理。清晰的解释比只给我有效的代码要好十倍。 /* b
我有一个 ajax 调用,我想在完成解析并将结果动画化到页面中后调用它。这就是我陷入困境的地方。 我能记忆起这个功能,但它似乎没有考虑到动画的延迟。即控制台不断以疯狂的速度输出值。 我认为 setIn
有人愿意用通俗易懂的语言逐步解释这个程序(取自书籍教程)以帮助我理解递归吗? var reverseArray = function(x,indx,str) { return indx == 0 ?
目标是找出数组中整数的任意组合是否等于数组中的最大整数。 function ArrayAdditionI(arr) { arr.sort(function(a,b){ return a -
我在尝试获取 SQL 查询所需的所有数据时遇到一些重大问题。我对查询还很陌生,所以我会尽力尽可能地描述这一点。 我正在尝试使用 Wordpress 插件 NextGen Gallery 进行交叉查询。
虽然网上有很多关于递归的信息,但我还没有找到任何可以应用于我的问题的信息。我对编程还是很陌生,所以如果我的问题很微不足道,请原谅。 感谢您的帮助:) 这就是我想要的结果: listVariations
我一整天都在为以下问题而苦苦挣扎。我一开始就有问题。我不知道如何使用递归来解决这个特定问题。我将非常感谢您的帮助,因为我的期末考试还有几天。干杯 假设有一个包含“n”个元素的整数数组“a”。编写递归函
我有这个问题我想创建一个递归函数来计算所有可能的数字 (k>0),加上数字 1 或 2。数字 2 的示例我有两个可能性。 2 = 1+1 和 2 = 2 ,对于数字 3 两个 poss。 3 = 1+
目录 递归的基础 递归的底层实现(不是重点) 递归的应用场景 编程中 两种解决问题的思维 自下而上(Bottom-Up) 自上而下(Top-
0. 学习目标 递归函数是直接调用自己或通过一系列语句间接调用自己的函数。递归在程序设计有着举足轻重的作用,在很多情况下,借助递归可以优雅的解决问题。本节主要介绍递归的基本概念以及如何构建递归程序。
我有一个问题一直困扰着我,希望有人能提供帮助。我认为它可能必须通过递归和/或排列来解决,但我不是一个足够好的 (PHP) 程序员。 $map[] = array("0", "1", "2", "3")
我有数据 library(dplyr, warn.conflicts = FALSE) mtcars %>% as_tibble() %>% select(mpg, qsec) %>% h
在 q 中,over 的常见插图运算符(operator) /是 implementation of fibonacci sequence 10 {x,sum -2#x}/ 1 1 这确实打印了前 1
我试图理解以下代码片段中的递归调用。 static long fib(int n) { return n <= 1 ? n : fib(n-1) + fib(n-2); } 哪个函数调用首先被
我是一名优秀的程序员,十分优秀!