GRjun @ 2021-07-27 21:21:59
#include<bits/stdc++.h>
using namespace std;
int a[31][31],flag=0,n,s=0;
bool b[31][31];
int q[1000][3];
int head,tail;
int x2[901],y2[901];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void bfs(int sx,int sy)
{
flag=0;
q[1][1]=sx;
q[1][2]=sy;
x2[s]=sx;
y2[s]=sy;
head=0,tail=1,s=1;
b[sx][sy]=1;
while(head!=tail)
{
head++;
int x=q[head][1],y=q[head][2];
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if((xx==1||xx==10||yy==1||yy==10)&&a[xx][yy]==0)
flag=1;
if(xx>1&&yy>1&&xx<10&&yy<10&&b[xx][yy]==0&&a[xx][yy]==0)
{
b[xx][yy]=1;
tail++;
s++;
q[tail][1]=xx;
q[tail][2]=yy;
x2[s]=xx;
y2[s]=yy;
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
if(a[i][j]==0&&b[i][j]==0)
{
bfs(i,j);
if(flag==0)
{
for(int i=1;i<=s;i++)
a[x2[i]][y2[i]]=2;
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
return 0;
}by WangYinxiAlex @ 2023-07-31 14:50:14
@GRjun
发点自己的想法：
#include<iostream>
using namespace std;
int a[31][31];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cin>>a[i][j];
}
for(int i=2;i<n;i++){
for(int j=2;j<n;j++){
if(a[i][j]!=1)a[i][j]=2;
}
}
for(int i=2;i<n;i++){
for(int j=2;j<n;j++){
if(a[i][j]!=1&&\
(a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
a[i][j]=0;
}
}
}
for(int i=n-1;i>1;i--){
for(int j=n-1;j>1;j--){
if(a[i][j]!=1&&\
(a[i-1][j]==0||a[i][j-1]==0||a[i+1][j]==0||a[i][j+1]==0)){
a[i][j]=0;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cout<<a[i][j]<<" ";
cout<<endl;
}
return 0;
}注释：
10-14行：由于最多矩形的边缘也是在最外面一周，所以最外面的0肯定都不是矩阵内的。
15-23行：从左、上方向判断这个点四周是不是有矩形外的点（0），如果有，说明这个点也不是矩形内的。
24-32行：但只从左、上方向看是不够的（如图1，这个是左、上方向的漏洞），还得从右、下方向判断。
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 1 0 0 1 1 1
1 0 1 0 0 0 0 0
1 0 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1
图1
（第3行第2列、第3行第3列、第4行第2列、第4行第3列、第4行第4列均无法被赋值）按照这个办法，可以AC。
如果AC了，别忘了关注哦~