题解 | 小红走象步

#include <iostream>
#include<queue>
#include<vector>
using namespace std;

struct Node{
    int x,y,step;
    Node(int x_,int y_,int step_):x(x_),y(y_),step(step_){}
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    int k;
    cin>>k;
    vector<vector<char>>grid(n,vector<char>(m,'.'));
    for(int i=0;i<k;i++){
        int x,y;
        cin>>x>>y;
        x--;
        y--;
        grid[x][y]='*';
    }
    vector<vector<bool>>visited(n,vector<bool>(m,false));
    queue<Node>q;
    int xs,ys,xt,yt;
    cin>>xs>>ys>>xt>>yt;
    xs--;
    ys--;
    xt--;
    yt--;
    q.push(Node(xs,ys,0));
    visited[xs][ys]=true;
    int dirs[4][2]={{-2,-2},{-2,2},{2,-2},{2,2}};
    int res=-1;
    while(!q.empty()){
        Node curr=q.front();
        q.pop();
        if(curr.x==xt&&curr.y==yt){
            res=curr.step;
            break;
        }
        for(auto&d:dirs){
            int x=curr.x+d[0];
            int y=curr.y+d[1];
            int eyex=curr.x+d[0]/2;
            int eyey=curr.y+d[1]/2;
            if(x<0||x>=n||y<0||y>=m||grid[eyex][eyey]=='*'||visited[x][y])continue;
            visited[x][y]=true;
            q.push(Node(x,y,curr.step+1));
        }
    }
    cout<<res<<endl;
    return 0;
}