dfs
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 50;
char g[N][N];
bool st[N][N];
int n, m;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int dfs(int x, int y)
{
int cnt = 1; //起点算一个
st[x][y] = true;
//向四周查找
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) continue;
if (g[a][b] != '.') continue;
if (!st[a][b]) // 还没有被搜索过
cnt += dfs(a, b); // 继续搜索
}
return cnt;
}
int main()
{
//多组输入,知道输入的结果为0 0,停止
while (cin >> m >> n, n || m) //m是列数,n是行数
{
for (int i = 0; i < n; i++) cin >> g[i];
//起点的位置(x,y)
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) << '\n';
//每次操作完后将st[][]重置为0
memset(st, 0, sizeof st);
}
return 0;
}
bfs
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 30;
char g[N][N];
bool st[N][N];
int n, m;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int main()
{
while (cin >> m >> n, n || m)
{
// 读入
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;
}
// 定义队列,起点入队
queue<PII> q;
q.push({ x,y });
st[x][y] = true;
while (q.size())
{
//取队首,弹出
auto t = q.front();
q.pop();
//向四周查找
for (int i = 0; i < 4; i++)
{
int a = dx[i] + t.x, b = dy[i] + t.y; // dx[] dy[] 表示查找的方向!!
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (g[a][b] != '.') continue;
if (!st[a][b])
{
q.push({ a,b }), st[a][b] = true;
//cout << "@ ";
}
}
}
int res = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (st[i][j]) res++;
cout << res << '\n';
memset(st, 0, sizeof st);
}
return 0;
}