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
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N = 10 + 5;typedef struct node{    int x,y,step;    bool operator <(const node x) const {        return step > x.step;    }}Node;int x1,y1,x2,y2,x3,y3;bool visit[N][N];void Init(){    memset(visit,0,sizeof(visit));    visit[x3][y3] = true;}const int dir[8][2]={
    {
    1,0},{-1,0},{
    0,1},{
    0,-1},{
    1,1},{-1,1},{
    1,-1},{-1,-1}};int BFS(){    priority_queue
          
            Q;    Node t,s;    t.x = x1,t.y = y1,t.step = 0;    Q.push(t);    visit[t.x][t.y] = true;    while(!Q.empty()){        t = Q.top();Q.pop();        if(t.x == x2 && t.y == y2) return t.step;        for(int d=0;d<8;d++){            int newx = t.x + dir[d][0];            int newy = t.y + dir[d][1];            if(newx <= 0|| newx > 8 || newy <=0 || newy>8|| visit[newx][newy] ) continue;            s.x = newx,s.y = newy,s.step = t.step+1;            visit[s.x][s.y] = true;            Q.push(s);        }    }    return -1;}int main(){    int Case = 0;    while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3){        Init();        printf("Case %d: %d\n",++Case,BFS());    }}