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

灰太狼 2022-06-12 01:00 202阅读 0赞

![1550693635481eef6e48a9296ff05502_v_1499755977][]

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;
    }

[1550693635481eef6e48a9296ff05502_v_1499755977]: https://odzkskevi.qnssl.com/1550693635481eef6e48a9296ff05502?v=1499755977