I have improved my code, considered cases memtioned above,

and I think my programme can handle them, but still received

wrong answer

, can anyone give some tests or point my error?

Thanks.

here is my code in C++:

Code: Select all

```
#include "stdio.h"
int m,n,p,c[210][210],p2,neigh[101];
char map[210][210];
int cy[4]={0,1,0,-1},cx[4]={1,0,-1,0};
bool link[102][102];
void dfs(int y,int x,int cnum)
{
int i,ty,tx;
c[y][x]=cnum;
for(i=0;i<4;i++)
{
ty=y+cy[i];
tx=x+cx[i];
if(ty>0&&ty<=m&&tx>0&&tx<=n&&c[ty][tx]==0&&map[ty][tx]==map[y][x])dfs(ty,tx,cnum);
}
}
void decidelink(int y,int x)
{
int ty,tx,i;
for(i=0;i<4;i++)
{
ty=y+cy[i];
tx=x+cx[i];
if(ty>0&&ty<=m&&tx>0&&tx<=n)
{
link[c[y][x]][c[ty][tx]]=true;
link[c[ty][tx]][c[y][x]]=true;
}
else
{
link[0][c[y][x]]=true;
link[c[y][x]][0]=true;//frontier province;
}
}
}
void dijkstra()
{
bool visited[101];
int i,j,cur,mid,min[101],best[101];
for(i=1;i<=p;i++)
{
visited[i]=false;
if(link[0][i])min[i]=1;
else min[i]=30000;
}
min[0]=0;//start from frontier;
visited[0]=true;
while(1)
{
cur=30000;
for(j=0;j<=p;j++)
{
if(!visited[j]&&min[j]<cur)
{
cur=min[j];
mid=j;
}
}
if(cur==30000)break;//stop;
best[mid]=cur;
visited[mid]=true;
if(mid!=1)//not inside A;
{
for(j=0;j<=p;j++)
{
if(!visited[j]&&link[mid][j]&&cur+1<min[j])min[j]=cur+1;
}
}
}
for(i=1;i<=p2;i++)if(!visited[neigh[i]])break;
if(i>p2&&visited[1])printf("%d\n",best[1]+p2-2);
else printf("-1\n");;//has an unreachable neighour inside A;
}
int main()
{
char nouse[100];
int i,j;
//freopen("10607.in","r",stdin);
//freopen("10607.out","w",stdout);
while(1)
{
scanf("%d%d",&m,&n);
gets(nouse);
if(m==0&&n==0)break;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=0;
scanf("%c",&map[i][j]);
}
gets(nouse);
}
p=1;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(c[i][j]==0)
{
if(map[i][j]=='A')dfs(i,j,1);//1 stands for capital province;
else
{
if(map[i][j]>32)
{
p++;
dfs(i,j,p);
}
else c[i][j]=101;//illegal char, thus not a country;
}
}
}
}//decide the countries;
for(i=0;i<=p;i++)for(j=0;j<=p;j++)link[i][j]=false;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{decidelink(i,j);}
}
p2=0;
for(i=2;i<=p;i++)
{
if(link[i][1])
{
p2++;//direct neighbour of capital province;
neigh[p2]=i;
}
}
dijkstra();
}
return 0;
}
```