好奇怪的游戏

清疚 2021-11-13 15:12 264阅读 0赞

### 题目背景 ###

《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。

### 题目描述 ###

爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：\*\*\*（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？

### 输入格式 ###

第1行：两个整数x1，y1

第2行：两个整数x2，y2

### 输出格式 ###

第1行：黑马到1,1的距离

第2行：白马到1,1的距离

### 输入输出样例 ###

输入 \#1复制

12 16
    18 10

输出 \#1复制

8 
    9

### 说明/提示 ###

100%数据：x1,y1,x2,y2<=20

依然是单调队列版子题

#include<cstdio>
    #include<cstring>
    int dx[12]={2,-2,2,-2,1,1,-1,-1,2,2,-2,-2};
    
    int dy[12]={2,2,-2,-2,2,-2,2,-2,1,-1,1,-1};
    
    int b[1001][1001],que[100001][3],a[1001][1001];
    
    int BFS(int x,int y){
        int tail=1,head=0;
        que[tail][0]=x;
        que[tail][1]=y;
        b[x][y]=1;
        do{
            head++;
            for (int i=0;i<12;i++){
                int x1=que[head][0]+dx[i];
                int y1=que[head][1]+dy[i];
                if (x1>=1 && x1<=50 && y1<=50 & y1>=1 && b[x1][y1]==0){
                    tail++; 
                    que[tail][0]=x1;
                    que[tail][1]=y1;
                    b[x1][y1]=1;
                    a[x1][y1]=a[que[head][0]][que[head][1]]+1;
                }
            }
        }while (head<tail);
        return a[1][1];
    }
    
    int main(){
        int x1,y1,i,j;
        scanf("%d%d",&x1,&y1);
        printf("%d\n",BFS(x1,y1));
        memset(b,0,sizeof(b)); 
        memset(que,0,sizeof(que));
        memset(a,0,sizeof(a));
        scanf("%d%d",&x1,&y1);
        printf("%d\n",BFS(x1,y1));
        return 0;
    }

转载于:https://www.cnblogs.com/ainiyuling/p/11194454.html