洪水填充递归算法

Question

你好，我利用洪水填充递归算法在2D数组中找到相互连接的细胞(这里我使用向量)。但是这对于一个边界测试用例

失败了。

#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]它没有变化。代码中一定有什么问题。

Answer 1

这里好像有个打字错误:

floodFill(a,i,j,2+i,m,m);

应:

floodFill(a,i,j,2+i,m,n);

除非你的矩阵是方阵。将矩阵抽象为一个知道自己维度的对象(见这里)可能是值得的。