使用两种方法分别实现 bfs 和 dfs (对比两种算法)
bfs 伪代码
while (队列非空)
{
取队头, t
枚举t 的4个邻格
if 格子是陆地,并且未被开发 (if 前面如果有必要 加上 if()....continue)
标记为已被开发;
插入队列;
}
bfs 核心代码
while(q.size()) { // 当队列不空时
auto t = q.front(); // 每次取出队头元素
q.pop(); //删掉队头元素
res++; // 从队列每出一个格子,或 '.',记录一下,个数++
for (int i = 0; i < 4; i++) { // 扩展一下4个方向(用偏移量的技巧)
int x = t.x + dx[i], y = t.y + dy[i]; // t.x , t.y 就是当前坐标,x, y 是从当前坐标沿当前方向走到下一位的坐标
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue; // 如果出界或已被走过
g[x][y] = '#'; // 可扩展
q.push({x, y}); // 对格子进行扩展,标记为走过了,并进队列
}
}
本题完整代码 (bfs)
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII; // 在algorithm 库中
const int N = 25;
char g[N][N]; // 表示输入的集合
int n, m;
int bfs(int sx, int sy) {
queue<PII> q;
q.push({sx, sy}); //将起点放入队列
g[sx][sy] = '#'; // 起点被搜索过,不可以走,标记为 #
int res = 0; // 所有可能搜到的(黑砖)的数量
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while(q.size()) { // 当队列不空时
auto t = q.front(); // 每次取出队头元素
q.pop(); //删掉队头元素
res++; // 从队列每出一个格子,或 '.',记录一下,个数++
for (int i = 0; i < 4; i++) { // 扩展一下4个方向(用偏移量的技巧)
int x = t.x + dx[i], y = t.y + dy[i]; // t.x , t.y 就是当前坐标,x, y 是从当前坐标沿当前方向走到下一位的坐标
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue; // 如果出界或已被走过
g[x][y] = '#'; // 可扩展
q.push({x, y}); // 对格子进行扩展,标记为走过了,并进队列
}
}
return res; // 最后res中存的值就是连通快里包含的 . 的数量
}
int main() {
while (cin >> m >> n, n || m) { // 多组测试数据,知道 (0,0)为止 先读入m代表列 n代表行
for (int i = 0; i < n; i++) cin >> g[i]; // 读入整个矩阵,每个g[i] 代表一行
int x, y; //人所在位置用 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 << bfs(x, y) << endl;
}
return 0;
}
时间复杂度 O(n * m)
代码改进(main函数可以这样写)
int main() {
while (cin >> m >> n, n || m) { // 多组测试数据,知道 (0,0)为止 先读入m代表列 n代表行
int x, y; //人所在位置用 x, y 表示
for (int i = 0; i < n; i++) {
cin >> g[i]; //在这里顺便读入数据,不用单独在外面写一个for
for (int j = 0; j < m; j++)
if (g[i][j] == '@') // 开始时人的位置
x = i, y = j;
}
cout << bfs(x, y) << endl;
}
return 0;
}
dfs 伪代码
dfs (x, y) {
将(x, y)标记为已开发
枚举(x, y) 的4个邻格
if 邻格可走(未出界)
dfs(邻格)
}
dfs 核心代码
int dfs(int x, int y) {
int res = 1; // 当前格子也可搜
g[x][y] = '#'; // (x, y)标记为已开发
for (int i = 0; i < 4; i++) { // 枚举周围4个邻格
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.') res += dfs(a, b); // 如果没有出界...。 (a,b)邻格
} // dfs(a, b); 是邻格可搜的
return res;
}
本体完整代码 (dfs)
#include <iostream>
using namespace std;
const int N = 25;
char g[N][N]; // 表示输入的集合
int n, m;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int dfs(int x, int y) {
int res = 1; // 当前格子也可搜
g[x][y] = '#'; // (x, y)标记为已开发
for (int i = 0; i < 4; i++) { // 枚举周围4个邻格
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.') res += dfs(a, b); // 如果没有出界...。 (a,b)邻格
} // dfs(a, b); 是邻格可搜的
return res;
}
int main() {
while (cin >> m >> n, n || m) { // 多组测试数据,知道 (0,0)为止 先读入m代表列 n代表行
int x, y; //人所在位置用 x, y 表示
for (int i = 0; i < n; i++) {
cin >> g[i]; //在这里顺便读入数据,不用单独在外面写一个for
for (int j = 0; j < m; j++)
if (g[i][j] == '@') // 开始时人的位置
x = i, y = j;
}
cout << dfs(x, y) << endl;
}
return 0;
}