优化一下,还需要加上vis数组来标记当前是否访问过此节点。避免一个节点多次入队。
by ag38821 @ 2024-04-09 11:47:01
```cpp
#include<bits/stdc++.h>
using namespace std;
queue<pair<int, int>> que;
char ch;
int n, m, cnt, a[510][510];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = { 0, 0, 1, 0, -1};
void bfs(int x, int y){
que.push(pair<int, int>(x, y));
a[x][y] = 1;
while(!que.empty()){
pair<int, int> t = que.front();
que.pop();
for(int i = 1; i <= 4; i++){
int xx = t.first + dx[i], yy = t.second + dy[i];
if(xx < 0 || yy < 0 || xx > n + 1 || yy > m + 1 || a[xx][yy] == 1)
continue;
else {
que.push(pair<int, int> (xx, yy));
a[xx][yy] = 1;
}
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++){
cin >> ch;
if(ch == '*') a[i][j] = 1;
}
}
bfs(0, 0);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++){
if(a[i][j] == 0) cnt++;
}
}
cout << cnt << endl;
return 0;
}
```
by ag38821 @ 2024-04-09 11:47:52
@[ag38821](/user/957039) 上述代码a数组就是vis标记数组的作用。
by ag38821 @ 2024-04-09 11:52:56