Gym - 100971A-DFS-值得思考-两种思路
韶云瀚
http://codeforces.com/gym/100971/problem/A
比赛中第一眼就看到这个了，当时以为是简单的搜索就完事了，后来发现还得枚举情况，就想了三种特判的条件，分别把模糊的地方当做陆地和海洋处理，如果都是1 那么就是ambiguous。
如果都大于1或者都等于0 肯定是不可以的。impossible.
其他情况哪个等于1 就置换哪个。
思路是没错的。
错误在搜索的地方，我开始在搜索判断小岛数量，只判断.的情况，因为’.’是合法的陆地。但是这样当两个问号相连时就出错了。比如
“####”
“.？？.”
“####”
“####”
” 就会出现 impossible。
但其实是可以的。。所以搜索时把?号也给搜索了就好了。
ps：开始以为是壮压来着，因为m,n都是很小的数字。。
并且每个??号都有可能是?和#.所以要枚举好多种情况哦
错就错在不用枚举情况的，为什么呢，如果把他们都成#,那么显然是错的。，那为什么当做.会是对的呢。
因为 都当成 . ，如果是出现两个岛屿的情况，会被条件pass。
而在一个岛屿内，你如果不是当前要判断的那个地方，你当成.和#和当前好想没啥关系啊。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn=200;
char a[maxn][maxn];
char b[maxn][maxn];
int m,n;
int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int dfs1(int a1,int b1)
{ if(a1>m||a1<1||b1>n||b1<1) return 0;
if(b[a1][b1]=='#') return 0;
b[a1][b1]='#';
for(int i=0;i<4;i++)
{ int xx=a1+fx[i][0];
int yy=b1+fx[i][1];
if(b[xx][yy]=='.') dfs1(xx,yy);
}
return 0;
}
int dfs()
{ int sum=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[i][j];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(b[i][j]=='.')
{ sum++;
dfs1(i,j);
}
return sum;
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
bool flag=false;
bool qq=false;
bool ss=false;
for(int i=1;i<=m;i++)
{for(int j=1;j<=n;j++)
{ if(a[i][j]=='?')
{a[i][j]='.';
int sum1=dfs();
a[i][j]='#';
int sum2=dfs();
if(sum1==1&&sum2==1){flag=true;break;}
else if(sum1>1&&sum2>1) {qq=true;break;}
else if(sum1==0&&sum2==0) {ss=true;break;}
else
{
if(sum1==1) a[i][j]='.';
else a[i][j]='#';
}
}
}
if(flag||qq||ss) break;
}
if(flag)
puts("Ambiguous");
else if(qq)
puts("Impossible");
else if(ss)
puts("Impossible");
else
{ for(int i=1;i<=m;i++)
{for(int j=1;j<=n;j++)
printf("%c",a[i][j]);
printf("\n");
}
}
return 0;
}‘看了别人的代码，比我的更好理解。。
他是通过判断数量来推断的。
不成立的条件就是存在两个.. 可以直接除去
存在ambigous的情况是当一个地方的改变不影响连通度（只改变一个当然正常，若是改变很多就是说明这个点是桥。是不能改变的。）
其他情况就正常输出。
这道题和我卡的数据都不一样，错误在于判断相等后（相等就是说这个问号没在大陆里）,可以直接跳出的
没有.的话，
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
/*看了别人的代码，和我判断的方式不一样，
他是通过判断陆地的大小，来区分的。
我感觉我写得好，
因为我不太擅长计数相关。
*/
const int maxn=200;
int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool vis[maxn][maxn];
int all;
int m,n;
int b[maxn][maxn];
char a[maxn][maxn];
int sum;
int dfs(int a1,int b1)
{ if(a1<1||a1>m||b1>n||b1<1)
return 0;
sum++;
vis[a1][b1]=true;
for(int i=0;i<4;i++)
{ int xx=a1+fx[i][0];
int yy=b1+fx[i][1];
if(!vis[xx][yy]&&b[xx][yy])
dfs(xx,yy);
}
return 0;
}
int main()
{ int k1,k2;
memset(vis,false,sizeof(vis));
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{cin>>a[i][j];
if(a[i][j]=='.') {b[i][j]=1;k1=i;k2=j;}
else if(a[i][j]=='?') b[i][j]=2;
}
int s=0;
memset(vis,false,sizeof(vis));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{ if(b[i][j]==1&&!vis[i][j])
{sum=0;
dfs(i,j);
s++;}
}
bool flag=false;
if(s>1)
{ puts("Impossible");return 0;
}
else
{ int all=sum;
for(int i=1;i<=m&&!flag;i++)
for(int j=1;j<=n&&!flag;j++)
{ if(b[i][j]==2)
{b[i][j]=0;
sum=0;
memset(vis,false,sizeof(vis));
dfs(k1,k2);
//cout<<sum<<endl;
if(sum==all) continue;
if(sum==all-1){flag=true;break;}
else b[i][j]=1;}
}
}
if(flag)
puts("Ambiguous");
else
{ for(int i=1;i<=m;i++)
{for(int j=1;j<=n;j++)
{ if(b[i][j])
cout<<'.';
else if(b[i][j]==0)
cout<<'#';
}
cout<<endl;
}
}
return 0;
}
类似资料：