洪水填充算法 - 房間面積

Question

有任務計算矩陣中的房間面積。第一個輸入是行和列位置的座標 - 零點是自由空間，1是牆。問題是，填充函數給我堆棧溢出異常。

#include<iostream> 
#include<conio.h> 
using namespace std; 

int a[5][5] = { {0,0,1,0,0}, 
       {0,0,1,0,0}, 
       {0,0,1,1,1}, 
       {1,1,1,0,0}, 
       {0,0,1,0,0}, 
}; 

bool vis[5][5] = { {0,0,0,0,0}, 
        {0,0,0,0,0}, 
        {0,0,0,0,0}, 
        {0,0,0,0,0}, 
        {0,0,0,0,0}, 
}; 
int c = 0; 

void flood(int row, int col){ 
    if(row < 0 || row > 4 || col < 0 || col > 4) 
     return; 
    if(a[row][col] == 0 && !vis[row][col]){ 
     c++; 
     vis[row][col] = 1; 
    } 
    flood(row-1, col); 
    flood(row+1, col); 
    flood(row,col-1); 
    flood(row, col+1); 
} 

int main(){ 
    int row, column; 
    cin>>row>>column; 

    flood(row,column); 
    cout<< c; 

    getch(); 
return 0; 
} 

Answer 1

如果您擊中了已經訪問的字段，則不應該遞歸。

在您的代碼中，這意味着擊中!vis[row][col]子句應阻止對flood的進一步遞歸調用。你可以簡單地通過在if內移動它們（或者更清楚一點，將所有東西移到外面並翻轉條件）來實現。這也可以防止當你碰到牆壁時發生遞歸，但這也是也是你想要什麼。