？为啥错了
原题链接：8003.拯救小码君
2024-05-23 13:43:17
发布于：广东
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
int x, y;
};
char mp[505][505];
bool vis[505][505];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};
int n, m, ct;
bool check(int x, int y){
if(x < 1 || x > n || y < 1 || y > m) return 0;
if(vis[x][y] || mp[x][y] == '*') return 0;
return 1;
}
bool bfs(int x, int y){
bool flag = 1;
queue <node> q;
q.push({x, y});
while(!q.empty()){
node head = q.front();
q.pop();
if(head.x == 1 || head.y == 1 || head.x == n || head.y == m) flag = 0;
for(int i = 0; i < 4; i++){
int xx = head.x + dir[i][0], yy = head.y + dir[i][1];
if(check(xx, yy)){
vis[xx][yy] = 1;
q.push({xx, yy});
}
}
}
return flag;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%s", mp[i] + 1);
}for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(mp[i][j] == '0' && !vis[i][j]){
vis[i][j] = 1;
ct += bfs(i, j);
}
}
}cout << ct;
return 0;
}
全部评论 4
答：用bfs触怒了dfs之神，简单代码如下：
#include <bits/stdc++.h>
using namespace std;
int n,m,sx,sy,fx,fy,d,jo;
char mg[501][501];
bool bfr[501][501];
#define check(x,y) (x>=1&&y>=1&&x<=n&&y<=m)
void dt(int x,int y){
bfr[x][y]=1;
if(xfx&&yfy) return;
if(x<n&&(mg[x+1][y]!=''&&!bfr[x+1][y])) {if(check(x+1,y)) d++;dt(x+1,y);}
if(y<m&&(mg[x][y+1]!=''&&!bfr[x][y+1])) {if(check(x,y+1)) d++;dt(x,y+1);}
if(y>1&&(mg[x][y-1]!=''&&!bfr[x][y-1])) {if(check(x,y-1)) d++;dt(x,y-1);}
if(x>1&&(mg[x-1][y]!=''&&!bfr[x-1][y])) {if(check(x-1,y)) d++;dt(x-1,y);}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i) for(int j=1;j<=m;j){
cin>>mg[i][j];
if(mg[i][j]=='*') jo;
}
for(int i=0;i<=n+1;++i) dt(i,0);
for(int i=1;i<=m+1;++i) dt(0,i);
for(int i=1;i<=m+1;++i) dt(n+1,i);
for(int i=1;i<=n;++i) dt(i,m+1);
cout<<n*m-jo-d;
return 0;
}
希望你能用你的智慧把dfs发扬光大1周前 来自 广东
0
有帮助，赞一个