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
这题其实就是模板题，类似于迷宫的，直接用BFS搜索就行
#include<cstdio>
#include<cstring> #include<queue> #include<stack> #include<iostream> using namespace std; int vis[8][8]; int dx[]={-1,1,0,0,-1,-1,1,1}; int dy[]={0,0,-1,1,-1,1,-1,1}; int r1,c1,r2,c2,r3,c3; int kstart ,kend; struct node { int x,y,step; }; queue<node>Q; int BFS(int x1,int y1) { while(!Q.empty()) Q.pop(); node u,next; u.x = x1; u.y = y1; u.step = 0; vis[u.x][u.y] = 1; Q.push(u); while(!Q.empty()) { node front = Q.front(); Q.pop(); if(front.x == r2&&front.y == c2) { return front.step; } int r = front.x; int l = front.y; for(int i=0;i<8;i++) { int nx = r+dx[i]; int ny = l+dy[i]; next.x =nx; next.y = ny; if(nx<0||ny<0||nx>=8||ny>=8||vis[nx][ny] == 1||(nx==r3&&ny==c3)) continue; vis[nx][ny] = 1; next.step = front.step + 1; Q.push(next); } } return -1; } int main() { int count1 = 1; while(~scanf("%d%d%d%d%d%d",&r1,&c1,&r2,&c2,&r3,&c3)) { memset(vis,0,sizeof(vis)); int ans; r1--,c1--,r2--,c2--,r3--,c3--; ans = BFS(r1,c1); printf("Case %d: %d\n",count1++,ans); } return 0; }