ACM 10102 Q10102: The path in the colored field
作法: BFS
/*************************************************************/
#include<stdio.h>
#include<stdlib.h>
main()
{
int n;
char x[101];
while(scanf("%d",&n)==1)
{
int a,b,c,d;
int map[102][102]={0};
for(a=0;a<n;a++)
{
scanf("%s",x);
for(b=0,c=1;b<n;b++,c++)
map[a+1][c]=x[b];
}
int max=0;
for(a=1;a<=n;a++)
for(b=1;b<=n;b++)
if(map[a][b]=='1')
{
int queue[10001][2]={0},top=0,appear[102][102]={0},ans;
queue[0][0]=a;queue[0][1]=b;
for(c=0;c<=top;c++)
{
int x=queue[c][0],y=queue[c][1];
if(map[x][y]=='3') {ans=appear[x][y];break;}
if(map[x+1][y]!=0&&appear[x+1][y]==0)
{
top++;
queue[top][0]=x+1;
queue[top][1]=y;
appear[x+1][y]=appear[x][y]+1;
}
if(map[x][y+1]!=0&&appear[x][y+1]==0)
{
top++;
queue[top][0]=x;
queue[top][1]=y+1;
appear[x][y+1]=appear[x][y]+1;
}
if(map[x-1][y]!=0&&appear[x-1][y]==0)
{
top++;
queue[top][0]=x-1;
queue[top][1]=y;
appear[x-1][y]=appear[x][y]+1;
}
if(map[x][y-1]!=0&&appear[x][y-1]==0)
{
top++;
queue[top][0]=x;
queue[top][1]=y-1;
appear[x][y-1]=appear[x][y]+1;
}
}
if(ans>max) max=ans;
}
printf("%d\n",max);
}
return 0;
}