红与黑
长方形矩阵中有两类点,一类可以走另一类不可以走,计算以某点为起点可以走过的点的数量。
Flood Fill算法(O(n*m)n、m为矩阵长宽)
-
宽搜bfs
输入:.可走,#不可走,@为起点
|---------> Y轴为宽w
|6 9
|....#.
|.....#
|......
|......
|......
|......
|......
|#@…#
|.#..#.
|0 0
↓
X轴为高h输出:
45
思路:Flood Fill算法,维护一个队列,开始时只有起点在队中,从起点开始,点每走一步上下左右四个方向判断是否合法,合法则放入队列中,并标记点为不可达。循环所有队中元素,每次取出队头元素循环判断其邻点,直到队列为空退出循环。因为只有可达点才会进入队列,因此每次出队可达点数量加1,队空时得到结果。
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 25;
int w, h; //宽度和高度(列数和行数)
char f[N][N];
int bfs(int sx, int sy) //起点位置
{
queue<pair<int,int>> q;
q.push({sx,sy}); //起点入队
f[sx][sy] = '#';
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int res = 0;
while(q.size())
{
auto t = q.front(); //取出队头元素
q.pop(), res++; //凡是被放进队列中的,均为可以走的,出队一次,res++
for(int i = 0; i < 4; i++)
{
int x = t.first + dx[i], y = t.second + dy[i];
if(x < 0 || x >= h || y < 0 || y > w || f[x][y] != '.') continue; //不可以走,换方向
f[x][y] = '#'; //可以走,点标记为走过了
q.push({x,y});
}
}
return res;
}
int main()
{
while(cin >> w >> h, w || h)
{
for(int i = 0; i < h; i++) cin >> f[i];
int x, y; //起点
for(int i = 0; i < h; i++) //遍历每行每列,找到起点
for(int j = 0; j < w; j++)
if(f[i][j] == '@')
x = i, y = j;
cout << bfs(x,y) << endl;
}
return 0;
}