题目描述
地砖有红和黑两种颜色,站在给定的某个黑色地砖上,问有多少块黑色地砖可达?
f1 dfs计算连通性 |
基本分析
- dfs返回什么?从当前节点出发可达的黑色地砖个数
- dfs怎么实现?
- 初始化cnt;
- 修改vis状态;
- 枚举可选的4相邻地砖(越界跳过,访问过跳过,红色跳过,累加下一步可达的个数)
- 返回cnt
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
int m, n;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
bool vis[N][N];
char g[N][N];
int dfs(int x, int y)
{
int cnt = 1;
vis[x][y] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (g[nx][ny] == '#') continue;
if ( nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny]) continue;
cnt += dfs(nx, ny);
}
return cnt;
}
int main()
{
while (cin >> m >> n, m || n)
{
for (int i = 0; i < n; i++) cin >> 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;
memset(vis, 0, sizeof vis);
cout << dfs(x, y) << endl;
}
return 0;
}
总结
- 这里n和m不同,怎么定义g和vis?直接给一个大的N
- 这里m和n的含义?m是横向,n是纵向。放到坐标中向右是y,向下是x
- 不能忘记初始化vis数组