Algorithme récursif de remplissage d'inondation

Question

Bonjour J'ai utilisé l'algorithme récursif de remplissage d'inondation pour trouver les cellules connectées les unes aux autres dans un tableau 2D (ici j'utilise des vecteurs). Mais cela ne fonctionne pas pour un cas de test limite

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

}

Et c'est le cas de test d'entrée pour laquelle il ne parvient pas

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 

Et ceci est sortie donnée par le code

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 

Mais la sortie devrait être 29, pour [1,8] [3,8] et [6,8] il ne change pas. Quel doit être le problème dans le code.

Answer 1

On dirait une faute de frappe ici:

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

devrait être:

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

À moins que votre matrice est carrée. Il peut être utile de faire abstraction de la matrice dans un objet qui connaît ses propres dimensions (see here). Ensuite, vous pouvez passer moins de paramètres partout.