BFS做法(y总模板)
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
char g[N][N];
int st[N][N];
int n, m;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int bfs(PII start)
{
int cnt = 1;
queue<PII> q;
q.push(start);
st[start.x][start.y] = 1;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int x = t.x + dx[i], y = t.y + dy[i];
if(x < 0 || x >= m || y < 0 || y >= n) continue;
if(g[x][y]!='.') continue;
if(st[x][y] == 1) continue;
st[x][y]=true;
q.push({x, y});
cnt++;
}
}
return cnt;
}
int main()
{
PII start;
while(cin >> n >> m, n || m)
{
for(int i = 0; i < m; i ++)
{
scanf("%s", g[i]);
}
for(int i = 0; i < m; i ++)
{
for(int j = 0; j < n; j ++)
{
if(g[i][j] == '@')
{
start = {i, j};
int res = bfs(start);
printf("%d\n", res);
}
}
}
memset(st, 0, sizeof(st));
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla