题目链接：
这道题是LITTLESUN写的第一道BFS哦！
对于这道题的的思路是把封闭图形外边的0标记一边，在最后输出的时候把没有标记过的0输出为2，其他按照原图输出。
对于这道题的的边界有两种判断方式。第一种是在原图外面加一圈0
AC代码如下：
#include#include #include #include #include #include #define MAXN 2000 using namespace std;int G[MAXN][MAXN];bool vis[MAXN][MAXN];struct item{ int x; int y;};int n;item a;item t2;void bfs(){ queue - q; a.x=1; a.y=1; q.push(a); while(!q.empty()) { item t=q.front(); q.pop(); if(G[t.x+1][t.y]==0&&t.x!=n+2&&!vis[t.x+1][t.y]) { vis[t.x+1][t.y]=1; t2.x=t.x+1; t2.y=t.y; q.push(t2); } if(G[t.x-1][t.y]==0&&t.x!=1&&!vis[t.x-1][t.y]) { vis[t.x-1][t.y]=1; t2.x=t.x-1; t2.y=t.y; q.push(t2); } if(G[t.x][t.y+1]==0&&t.y!=n+2&&!vis[t.x][t.y+1]) { vis[t.x][t.y+1]=1; t2.x=t.x; t2.y=t.y+1; q.push(t2); } if(G[t.x][t.y-1]==0&&t.y!=1&&!vis[t.x][t.y-1]) { vis[t.x][t.y-1]=1; t2.x=t.x; t2.y=t.y-1; q.push(t2); } } } int main(){ scanf("%d",&n); for(int i=2;i<=n+1;i++) { for(int j=2;j<=n+1;j++) { scanf("%d",&G[i][j]); } } bfs(); for(int i=2;i<=n+1;i++) { for(int j=2;j<=n+1;j++) { if(!vis[i][j]&&G[i][j]==0) { G[i][j]=2; } } } for(int i=2;i<=n+1;i++) { //cout<
另一种方法是枚举边界每一个不是一的点作为起点进行BFS
但这个代码不知道哪里锅掉了，只有80分qwq
代码如下：
#include#include #include #include #include #include #define MAXN 2000 using namespace std;int G[MAXN][MAXN];bool vis[MAXN][MAXN];struct item{ int x; int y;};int n;item a;queue - q;void bfs(item b){ q.push(b); while(!q.empty()) { item t=q.front(); q.pop(); if(G[t.x+1][t.y]==0&&t.x!=n&&!vis[t.x+1][t.y]) { vis[t.x+1][t.y]=1; t.x=t.x+1; t.y=t.y; q.push(t); } if(G[t.x-1][t.y]==0&&t.x!=1&&!vis[t.x-1][t.y]) { vis[t.x-1][t.y]=1; t.x=t.x-1; t.y=t.y; q.push(t); } if(G[t.x][t.y+1]==0&&t.y!=n&&!vis[t.x][t.y+1]) { vis[t.x][t.y+1]=1; t.x=t.x; t.y=t.y+1; q.push(t); } if(G[t.x][t.y-1]==0&&t.y!=1&&!vis[t.x][t.y-1]) { vis[t.x][t.y-1]=1; t.x=t.x; t.y=t.y-1; q.push(t); } }} void work(){ for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if((i==1||i==n||j==1||j==n)&&G[i][j]!=1) { a.x=i; a.y=j; bfs(a); } } }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&G[i][j]); } } work(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(!vis[i][j]&&G[i][j]==0) { G[i][j]=2; } } } for(int i=1;i<=n;i++) { //cout<