forgery
题目 Forgery
思路分析
其实和染色法没任何关系 一道枚举题
可以染色无数次，那么应该很容易想到，只要出现了一个点在目标图中是被 # 围成了一个圈的并且周围一圈都没有越界，那么就在当前图中染掉，然后去到下一个点。
全部染完之后与目标图比对一下就行了，一样就输出 YES ,反之则 NO 。
策略很简单，但是找到满足条件的点有两种方法：枚举或深搜。
枚举比dfs时空都要优些
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1005;
char went[N][N],now[N][N];
int dx[8]={0,0,1,1,-1,-1,1,-1};
int dy[8]={1,-1,1,-1,1,-1,0,0};
int n,m;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>went[i][j];
now[i][j]='.';
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
bool flag=false;
for(int k=0;k<=7;k++){
int nx=i+dx[k],ny=j+dy[k];
if(nx<=0 || nx>n || ny<=0 || ny>m || went[nx][ny]=='.'){
flag=true;
break;
}
}
if(flag)
continue;
for(int k=0;k<=7;k++){
int nx=i+dx[k],ny=j+dy[k];
now[nx][ny]='#';
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(went[i][j]!=now[i][j]){
cout<<"NO"<<endl;
return 0;
}
}
}
cout<<"YES"<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1005;
char went[N][N],now[N][N];
bool st[N][N];
int n,m;
int dx[8]={0,0,1,1,-1,-1,1,-1};
int dy[8]={1,-1,1,-1,1,-1,0,0};
bool isVaild(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m && !st[x][y];
}
void dfs(int x,int y){
bool flag=false;
for(int k=0;k<=7;k++){
int nx=x+dx[k],ny=y+dy[k];
if(nx<=0 || nx>n || ny<=0 || ny>m || went[nx][ny]=='.'){
flag=true;
break;
}
}
for(int k=0;k<=7;k++){
int nx=x+dx[k],ny=y+dy[k];
if(!flag)
now[nx][ny]='#';
if(isVaild(nx,ny)){
st[nx][ny]=true;
dfs(nx,ny);
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>went[i][j];
now[i][j]='.';
}
}
dfs(1,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(went[i][j]!=now[i][j]){
cout<<"NO"<<endl;
return 0;
}
}
}
cout<<"YES"<<endl;
return 0;
}
💬 评论