板橋高中98資訊能力競賽 最短距離
作法 : BFS擴張
從起點BFS擴張,若到終點則輸出,若沒辦法到達則輸出0
/***********************************************************/
#include<stdlib.h>
#include<stdio.h>
main()
{
int t,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
int map[101][101]={0},sx,sy,ex,ey,a,b,c;
char s[101];
scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
for(a=0;a<n;a++)
{
scanf("%s",s);
for(b=0;b<m;b++)
if(s[b]=='1') map[a][b]=-1;
}
int queue[10000][2]={0},top=0,find=0;
queue[0][0]=sx-1;queue[0][1]=sy-1;
for(a=0;a<=top;a++)
{
int xx=queue[a][0],yy=queue[a][1];
if(xx==ex-1&&yy==ey-1) {find=1;break;}
if(map[xx+1][yy]==0&&xx+1<n)
{
map[xx+1][yy]=map[xx][yy]+1;
top++;
queue[top][0]=xx+1;queue[top][1]=yy;
}
if(map[xx-1][yy]==0&&xx-1>=0)
{
map[xx-1][yy]=map[xx][yy]+1;
top++;
queue[top][0]=xx-1;queue[top][1]=yy;
}
if(map[xx][yy+1]==0&&yy+1<m)
{
map[xx][yy+1]=map[xx][yy]+1;
top++;
queue[top][0]=xx;queue[top][1]=yy+1;
}
if(map[xx][yy-1]==0&&yy-1>=0)
{
map[xx][yy-1]=map[xx][yy]+1;
top++;
queue[top][0]=xx;queue[top][1]=yy-1;
}
}
if(find==1)
printf("%d\n",map[ex-1][ey-1]+1);
else printf("0\n");
/* for(a=0;a<n;a++)
{
for(b=0;b<m;b++)
printf("%3d ",map[a][b]);
printf("\n");
}*/
}
return 0;
}
/*
2
5 6 3 1 3 4
000000
011101
000010
011000
000010
*/