P-残缺的棋盘

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<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

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<Node> 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
",++Case,BFS());
    }
}