ACM 439 Knight Moves
BFS是佇列的應用
也就是先進先出 DFS是堆疊 先進後出
之前文章的變數打錯`XD 請原諒我 我懶得改了
此題必須考慮棋盤的邊界問題 因為會有差別 害我吃WA
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main()
{
int n,m,a,b;
char x[3],y[3];
while(scanf("%s %s",x,y)==2)
{
if(strcmp(x,y)==0) {printf("To get from %s to %s takes 0 knight moves.\n",x,y);continue;}
char map[11][11]={0};
int ansx=y[0]-'a',ansy=y[1]-'1',startx=x[0]-'a',starty=x[1]-'1';
char queue[64][2]={0},top=0,ans;
map[ansx][ansy]=-1;
queue[0][0]=startx;queue[0][1]=starty;
for(a=0;a<=top;a++)
{
int nn=queue[a][0],mm=queue[a][1];
if(map[nn+2][mm+1]==-1||map[nn+2][mm-1]==-1||map[nn-1][mm+2]==-1||map[nn-1][mm-2]==-1||map[nn-2][mm+1]==-1||map[nn-2][mm-1]==-1||map[nn+1][mm-2]==-1||map[nn+1][mm+2]==-1)
{ans=map[nn][mm]+1;break;}
if(map[nn+2][mm+1]==0&&nn+2<8&&mm+1<8)
{
map[nn+2][mm+1]=map[nn][mm]+1;
top++;
queue[top][0]=nn+2;queue[top][1]=mm+1;
}
if(map[nn+2][mm-1]==0&&nn+2<8&&mm-1>=0)
{
map[nn+2][mm-1]=map[nn][mm]+1;
top++;
queue[top][0]=nn+2;queue[top][1]=mm-1;
}
if(map[nn-1][mm+2]==0&&nn-1>=0&&mm+2<8)
{
map[nn-1][mm+2]=map[nn][mm]+1;
top++;
queue[top][0]=nn-1;queue[top][1]=mm+2;
}
if(map[nn-1][mm-2]==0&&nn-1>=0&&mm-2>=0)
{
map[nn-1][mm-2]=map[nn][mm]+1;
top++;
queue[top][0]=nn-1;queue[top][1]=mm-2;
}
if(map[nn-2][mm+1]==0&&nn-2>=0&&mm+1<8)
{
map[nn-2][mm+1]=map[nn][mm]+1;
top++;
queue[top][0]=nn-2;queue[top][1]=mm+1;
}
if(map[nn-2][mm-1]==0&&nn-2>=0&&mm-1>=0)
{
map[nn-2][mm-1]=map[nn][mm]+1;
top++;
queue[top][0]=nn-2;queue[top][1]=mm-1;
}
if(map[nn+1][mm-2]==0&&nn+1<8&&mm-2>=0)
{
map[nn+1][mm-2]=map[nn][mm]+1;
top++;
queue[top][0]=nn+1;queue[top][1]=mm-2;
}
if(map[nn+1][mm+2]==0&&nn+1<8&&mm+2<8)
{
map[nn+1][mm+2]=map[nn][mm]+1;
top++;
queue[top][0]=nn+1;queue[top][1]=mm+2;
}
}
printf("To get from %s to %s takes %d knight moves.\n",x,y,ans);
}
return 0;
}