注册登录

残缺的棋盘 （BFS）

在国际象棋里，王是最重要的一个棋子。每一步，王可以往上下左右或者对角线方向移动一步，如下图所示

给定两个格子 A(r1c1) B(r2c2)，你的任务是计算出一个王从 A到 B至少需要走多少步。为了避免题目太简单，我们从棋盘里拿掉了一个格子 C(r3c3)（ABC保证互不相同），要求王从 A走到 B的过程中不能进入格子 C。在本题中，各行从上到下编号为 1~8，各列从左到右编号为1~8。

Input

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

Output

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

Sample Input

copy
1 1 8 7 5 6
1 1 3 3 2 2
知识兔

Sample Output

copy
Case 1: 7
Case 2: 3


知识兔

#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#define lli long long
#define mem(s,t) memset(s,t,sizeof(s))
#define ok return 0;
#define rep(x) for(int i=0;i<x;i++) cin>>a[i];
#define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int num[51 ];
int dir[8][2] = {1,0,-1,0,   0,1,0,-1,    1,1,1,-1,    -1,1,-1,-1};
 
struct node
{
    int x,y,t;
};
node a,b,c;
int vis[9][9];
void debug()
{
    for(int i=0; i<=8; i++)
    {
        for(int j=0; j<=8; j++)
            cout<<vis[i][j];
        cout<<endl;
    }
}
void BFS()
{
    queue<node>q;
    node now,nx;
    q.push(a);
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        if(now.x==b.x && now.y==b.y)
            break;
        for(int i=0; i<8; i++)
        {
            nx.x=now.x+dir[i][0];
            nx.y=now.y+dir[i][1];
            nx.t=now.t+1;
            if(nx.x<1 || nx.y<1 || nx.x>8|| nx.y>8) continue;
            if(!vis[nx.x][nx.y] )
            {
                q.push(nx);
                vis[nx.x][nx.y] = 1 ;
            }
        }
    }
    cout<<now.t<<endl;
}
int main()
{
    int tt=1;
    while(cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y)
    {
        a.t=0;
        mem(vis,0);
        vis[c.x][c.y]=1;
        vis[a.x][a.y]=1;
 
 
        cout<<"Case "<<tt++<<": ";
        BFS();
    }
}
知识兔
计算机