湖南省第十届大学生计算机程序设计竞赛----残缺的棋局

Input

输入包含不超过10000 组数据。每组数据包含6个整数r1, c1, r2, c2, r3, c3 (1<=r1, c1, r2, c2, r3, c3<=8). 三个格子A, B, C保证各不相同。

Output

对于每组数据，输出测试点编号和最少步数。

Sample Input 1 1 8 7 5 6 1 1 3 3 2 2

Sample Output

Case 1: 7 Case 2: 3

#include <algorithm> #include <cstdio> #include <queue> #include <cstring> using namespace std; int map1[10][10]; int sx,sy,ex,ey,zx,zy; struct A{ int x,y,step; }f,g; int dx[]={0,0,1,-1,1,1,-1,-1}; int dy[]={1,-1,0,0,1,-1,1,-1}; int bfs(int x,int y) { queue<A> Q; f.x=x; f.y=y; f.step=0; Q.push(f); map1[x][y]=1; while(!Q.empty()) { f=Q.front(); Q.pop(); if(f.x==ex&&f.y==ey) return f.step; for(int i=0;i<8;i++) { g.x=f.x+dx[i]; g.y=f.y+dy[i]; // if(g.x==ex&&g.y==ey) // return f.step+1; if(0<g.x&&g.x<=8&&0<g.y&&g.y<=8&&!map1[g.x][g.y]) { map1[g.x][g.y]=1; g.step=f.step+1; Q.push(g); } } } } int main() { int ca=1; while(~scanf("%d%d%d%d%d%d",&sx,&sy,&ex,&ey,&zx,&zy)) { memset(map1,0,sizeof(map1)); map1[zx][zy]=1; int ans=bfs(sx,sy); printf("Case %d: %d\n",ca++,ans); } return 0; }