题解 | 小红走象步

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int n, m, k;
int dir[4][2] = {{2, 2}, {-2, -2}, {2, -2}, {-2, 2}};

void work() 
{
    cin >> n >> m >> k;
   
    vector<vector<bool>> soldier(n + 1, vector<bool>(m + 1, false));
    // 使用 vector<bool> 压缩
    
    for(int i = 0; i < k; i++)
    {
        int x, y;
        cin >> x >> y;
        soldier[x][y] = true;
    }
    
    int x0, y0, xt, yt;
    cin >> x0 >> y0 >> xt >> yt;
    
    // 距离数组，-1表示未访问
    vector<vector<int>> dist(n + 1, vector<int>(m + 1, -1));
    
    queue<pair<int, int>> q;
    dist[x0][y0] = 0;
    q.push({x0, y0});
    
    while(!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        
        if(x == xt && y == yt)
        {
            cout << dist[x][y] << endl;
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            
            // 检查边界
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            
            // 检查是否已访问
            if(dist[nx][ny] != -1) continue;
            
            // 检查象眼位置是否有兵
            int mid_x = (x + nx) / 2;
            int mid_y = (y + ny) / 2;
            
            if(soldier[mid_x][mid_y]) continue;
            
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    
    cout << -1 << endl;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    while(t--) 
    {
        work();
    }
    return 0;
}