题解 P1747 【好奇怪的游戏】

徐上泽 · 2019-05-04 19:00:53 · 题解

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h> 
#define N 25
using namespace std;
struct node{
    int x,y,dis;
};
queue<node> qu;
int x1,y1,x2,y2;
bool mark[N+10][N+10];
int dxy[12][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1},{2,2},{2,-2},{-2,2},{-2,-2}};
int bfs(int x,int y){
    node u;
    u.x=x,u.y=y,u.dis=0;
    qu.push(u);
    while(!qu.empty()){
        u=qu.front();
        qu.pop();
        for(int i=0;i<12;i++){
            node v;
            v.x=u.x+dxy[i][0],v.y=u.y+dxy[i][1];
            if(v.x>=1&&v.y>=1&&v.x<=N&&v.y<=N&&!mark[v.x][v.y]){
                v.dis=u.dis+1;
                mark[v.x][v.y]=true;
                if(v.x==1&&v.y==1) return v.dis;
                qu.push(v);
            }
        }
    }
}
int main(){
    cin>>x1>>y1>>x2>>y2;
    cout<<bfs(x1,y1)<<endl;
    memset(mark,0,sizeof(mark));
    qu=queue<node>();
    cout<<bfs(x2,y2);
    return 0;
}