1459: Chess
Time Limit: 1 Sec Memory Limit:
128 MB Special Judge
Submit: 58 Solved: 31
[Submit][Status][Web
Board]
Description
Input
Output
Sample Input
3
E 2 E 3
F 1 E 8
A 3 A 3
Sample Output
Impossible
2 F 1 B 5 E 8
0 A 3
给出起点和终点,棋盘有两种颜色黑和白,跳的归则是只能跳到相同的颜色格子,问能跳到终到吗,能则输出跳的路径。
#include<stdio.h> #include<queue> #include<iostream> using namespace std; typedef struct nnn { int x,y,step; }NODE; int path[100],color; NODE node[2]; int bfs() { path[node[0].y*8+node[0].x]=node[0].y*8+node[0].x; if(node[0].x==node[1].x&&node[0].y==node[1].y) return 1; queue<NODE>q; NODE p,pre; int vist[10][10]={0}; int dir[4][2]={1,-1,-1,1,1,1,-1,-1}; node[0].step=0; vist[node[0].y][node[0].x]=1; q.push(node[0]); while(!q.empty()) { pre=q.front(); q.pop(); for(int e=0; e<4; e++) { p=pre; p.step++; for(int i=1; i<8; i++) { p.y=p.y+dir[e][0]*i; p.x=p.x+dir[e][1]*i; if(p.y>=0&&p.y<8&&p.x>=0&&p.x<8&&vist[p.y][p.x]==0) if(color==(p.y+p.x)%2) { path[p.y*8+p.x]=pre.y*8+pre.x; if(p.y==node[1].y&&p.x==node[1].x) return 1; vist[p.y][p.x]=1; if(p.step<3)q.push(p); } p.y=p.y-dir[e][0]*i; p.x=p.x-dir[e][1]*i; } p.step--; } } return 0; } int main() { int t,b,pp[100]; char s[2]; scanf("%d",&t); while(t--) { scanf("%s %d",s,&b);node[0].x=s[0]-'A';node[0].y=8-b; scanf("%s %d",s,&b);node[1].x=s[0]-'A';node[1].y=8-b; color=(node[0].y+node[0].x)%2; if(color!=(node[1].y+node[1].x)%2) printf("Impossible\n"); else { int flog=bfs(); if(flog==0) printf("Impossible\n"); else { int k=0,y; int x=node[1].y*8+node[1].x; while(path[x]!=x) { pp[k++]=x; x=path[x]; } pp[k++]=x; printf("%d",k-1); for(int i=k-1;i>=0; i--) { y=pp[i]/8; x=pp[i]%8; printf(" %c %d",x+'A',8-y); } printf("\n"); } } } }