社区讨论
问一下为什么第四个点过不了
P1162填涂颜色参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @locfapj2
- 此快照首次捕获于
- 2023/10/30 12:51 2 年前
- 此快照最后确认于
- 2023/11/05 00:29 2 年前
CPP
#include <cstdio>
#include <algorithm>
#include <queue>
#define noexced(x,y) (x>=0&&y>=0&&x<n&&y<n)
#define border(x,y) (x==0||y==0||x==n-1||y==n-1)
const int M=31,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
using namespace std;
short int g[M][M];
bool vis[M][M];
typedef struct {
int x,y;
}node;
int n,minrow[M],maxrow[M],mincol[M],maxcol[M];
int bfs(queue<node> q) {
int cnt=1;
while(!q.empty()) {
node now=q.front();
for(int i=0;i<4;i++) {
int nx=now.x+dx[i],ny=now.y+dy[i];
if(!vis[nx][ny]&&(noexced(nx,ny))&&g[nx][ny]==0) {
node New;
New.x=nx,New.y=ny;
vis[nx][ny]=1;
cnt++;
q.push(New);
}
}
q.pop();
}
return cnt;
}
// 边界存在连通块则不闭合
bool closed(void) {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(vis[i][j]&&border(i,j)) {
return 0;
}
}
}
return 1;
}
int main(){
//bool closed[M][M];
queue<node> q;
scanf("%d",&n);
for(int i=0;i<n;i++) {
//fill(closed[i],closed[i]+n+1,0);
for(int j=0;j<n;j++) {
scanf("%d",&g[i][j]);
}
}
for(int i=1;i<n-1;i++) {
for(int j=1;j<n-1;j++) {
if(g[i][j]==0&&!vis[i][j]) {
node fst;
fst.x=i,fst.y=j;
vis[i][j]=1;
q.push(fst);
bfs(q);
if(!closed()) { //如果不封闭
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(vis[i][j]) vis[i][j]=0;
}
}
}
else {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(vis[i][j]) g[i][j]=2;
}
}
}
}
}
}
for(int i=0;i<n;i++) {
printf("%d",g[i][0]);
for(int j=1;j<n;j++) {
printf(" %d",g[i][j]);
}
putchar('\n');
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...