题目描述
输入样例
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例
45
算法
Flood Fill(洪水灌溉算法)
BFS写法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
int n, m;
char g[N][N];
int dx[4] = { 0,-1,0,1 }, dy[4] = { -1,0,1,0 };
int bfs(PII start) {
int sum = 0;
g[start.x][start.y] = '#';
queue<PII> q;
q.push(start);
while (!q.empty()) {
PII k = q.front();
q.pop();
sum++;
for (int i = 0; i < 4; i++) {
int x = k.x + dx[i], y = k.y + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;
q.push(make_pair(x, y));
g[x][y] = '#';
}
}
return sum;
}
int main() {
while (cin >> m >> n , m || n) {
for (int i = 0; i < n; i++) scanf("%s", g[i]);
PII start;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '@') start = { i,j };
cout << bfs(start) << endl;
}
return 0;
}
DFS写法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 25;
int n, m;
char g[N][N];
int dx[4] = { 0,-1,0,1 }, dy[4] = { -1,0,1,0 };
int dfs(int x, int y) {
g[x][y] = '#';
int sum = 1;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.') sum += dfs(a, b);
}
return sum;
}
int main() {
while (cin >> m >> n, n || m) {
for (int i = 0; i < n; i++) scanf("%s", g[i]);
int x, y;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] == '@') x = i, y = j;
cout << dfs(x, y) << endl;
}
return 0;
}