您好，我使用了泛洪递归算法在二维数组中找到彼此连接的单元格（这里我使用向量）。但这对于一个边界测试用例来说是失败的
#include<iostream>
#include<vector>
using namespace std;
int count = 0;
int max_count = 0;
int min_count = 0;
void floodFillUtil(vector< vector<int> > &a,int i,int j,int m,int n,int prevP,int newN)
{
if (i<0 || i>= m || j<0 || j>=n)
return;
if(a[i][j] != prevP)
return;
count++;
a[i][j] = newN;
floodFillUtil(a,i+1,j+1,m,n,prevP,newN);
floodFillUtil(a,i-1,j-1,m,n,prevP,newN);
floodFillUtil(a,i-1,j+1,m,n,prevP,newN);
floodFillUtil(a,i+1,j-1,m,n,prevP,newN);
floodFillUtil(a,i+1,j,m,n,prevP,newN);
floodFillUtil(a,i,j+1,m,n,prevP,newN);
floodFillUtil(a,i-1,j,m,n,prevP,newN);
floodFillUtil(a,i,j-1,m,n,prevP,newN);
}
void floodFill(vector< vector<int> > &a,int i,int j,int newN,int m,int n) {
int prevP = a[i][j];
floodFillUtil(a,i,j,m,n,prevP,newN);
}
// Driver program to test above function
int main()
{ int m,n;
cin>>m>>n;
vector<vector<int> > a;
vector<int> b;
for(int i=0;i<m;i++)
{for(int j=0;j<n;j++)
{ int temp;
cin>>temp;
b.push_back(temp);
}
a.push_back(b);
b.clear();
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++) {
if (a[i][j] == 1){
floodFill(a,i,j,2+i,m,m);
min_count = count ;
if(min_count > max_count){
max_count = min_count;
}
count=0;
}
}
for(int i=0;i<m;i++)
{for(int j=0;j<n;j++)
cout<<a[i][j]<<" ";
cout<<endl;}
cout<<max_count;
}
这是它失败的输入测试用例
8
9
0 1 0 0 0 0 1 1 0
1 1 0 0 1 0 0 0 1
0 0 0 0 1 0 1 0 0
0 1 1 1 0 1 0 1 1
0 1 1 1 0 0 1 1 0
0 1 0 1 1 0 1 1 0
0 1 0 0 1 1 0 1 1
1 0 1 1 1 1 0 0 0
这是由代码给出的输出
0 2 0 0 0 0 2 2 0
2 2 0 0 3 0 0 0 1
0 0 0 0 3 0 3 0 0
0 3 3 3 0 3 0 3 1
0 3 3 3 0 0 3 3 0
0 3 0 3 3 0 3 3 0
0 3 0 0 3 3 0 3 1
3 0 3 3 3 3 0 0 0
27
但是输出应该是29，对于[1,8][3,8]和[6,8]，它没有改变，代码中的问题是什么。
最佳答案
这里看起来像是输入错误：
floodFill(a,i,j,2+i,m,m);
应该是：
floodFill(a,i,j,2+i,m,n);
除非你的矩阵是平方的。将矩阵抽象成一个知道自己维数的对象可能是值得的（see here）。然后可以在任何地方传递较少的参数。
关于algorithm - 洪水填充递归算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31817445/