AcWing 1113. 红与黑(C++ bfs)
原题链接
简单
关于读入
- 对于结尾是0 0 才停止读入的数据,可以这样读入
while(cin >> m >> n, n || m)
- bfs写了一下。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 30, M = N * N;
PII q[M];
char g[N][N];
bool st[N][N];
int n, m;
int bfs(int sx, int sy){
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
int cnt =1;
while( hh <= tt){
auto t = q[ hh ++];
for(int i = 0; i < 4; i ++){
int a = t.x + dx[i], b = t.y + dy[i];
if( a < 0 || a >= n || b < 0 || b >= m || st[a][b] || g[a][b] == '#') continue;
cnt ++;
st[a][b] = true;
q[++ tt] = {a,b};
}
}
return cnt;
}
int main(){
while(cin >> m >> n, n || m){
memset(st, 0, sizeof st);
for(int i = 0; i< n ;i ++) cin >> g[i];
for(int i = 0; i < n; i ++)
for(int j = 0; j< m; j ++)
if( g[i][j] == '@'){
cout << bfs(i ,j) << endl;
}
}
}