c++ - 洪水填充算法 - 房间面积

Question

任务是计算矩阵中的房间面积。第一个输入是行和列位置的坐标 - 零是自由空间，1 - 是墙壁。问题是 flood fill 函数给我 Stack overflow 异常。

#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 中即可实现(或者更清楚一点，将所有内容移到外面并翻转条件)。这也将防止在您撞墙时发生递归，但这也是您想要的。