algorithm - 洪水填充递归算法

Question

你好，我使用了 flood fill 递归算法来查找二维数组中相互连接的单元格(这里我使用的是矢量)。但这对于一个边界测试用例失败了

#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);

除非你的矩阵是正方形的。将矩阵抽象为一个知道其自身维度的对象 ( see here ) 可能是值得的。然后你可以在任何地方传递更少的参数。