江户川コナン @ 2021-07-26 18:03:59
代码:
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
node(int xx,int yy){
x=xx;
y=yy;
}
};
const int maxn=35;
int d[5][2]={{-1,0},{1,0},{0,-1},{0,1}};
int a[maxn][maxn];
bool b[maxn][maxn];
int n;
bool in(int dx,int dy){
return (dx>=1)&&(dx<=n)&&(dy>=1)&&(dy<=n);
}
void bfs(int x,int y){
queue<node> q;
q.push(node(x,y));
//cout<<x<<" "<<y<<endl;
b[x][y]=true;
while(!q.empty()){
node now=q.front();
q.pop();
for(int i=1;i<=4;i++){
int dx=now.x+d[i][0];
int dy=now.y+d[i][1];
if(in(dx,dy)&&!b[dx][dy]&&a[dx][dy]!=1){
q.push(node(dx,dy));
//cout<<dx<<" "<<dy<<endl;
b[dx][dy]=true;
}
}
}
}
int main(){
cin>>n;
//memset(a,1,sizeof a);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
//cout<<1<<endl;
for(int i=1;i<=n;i++){
if(a[1][i]==0 &&!b[1][i]){
bfs(1,i);
}
//cout<<1<<endl;
if(a[n][i]==0&&!b[n][i]){
bfs(n,i);
}
//cout<<2<<endl;
if(a[i][1]==0&&!b[i][1]){
bfs(i,1);
}
//cout<<3<<endl;
if(a[i][n]==0&&!b[i][n]){
bfs(i,n);
}
//cout<<4<<endl;
}
//bfs();
//cout<<1<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]!=1&&!b[i][j]){
cout<<2<<" ";
}else{
cout<<a[i][j]<<" ";
}
}
cout<<endl;
}
return 0;
}
大致思路是说用BFS将不被包围的0全部标记起来,然后没被标记的0输出2,其他照旧
恳请各位大佬指点迷津
by WangYinxiAlex @ 2023-07-31 14:51:22
@江户川コナン
发点自己的想法:
#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了,别忘了关注哦~