9-21华为笔试题解

#include <iostream>
#include <string.h>
#include <queue>
const int maxn = 1e3 + 5;
using namespace std;
int m, n;
char mp[maxn][maxn], vis[maxn][maxn][2];
int bx[] = {0, -1, 0, 1}, by[] = {-1, 0, 1, 0};
int mx[] = {-1, -2, -2, -1, 1, 2, 2, 1}, my[] = {-2, -1, 1, 2, 2, 1, -1, -2};

struct piece {
    piece(int a, int b, int c, int d): p(a), x(b), y(c), steps(d){}
    piece() {}
    int p;      // 类型
    int x, y;   // 坐标
    int steps;  // 步数
};

void init() {
    memset(vis, 0, sizeof(vis));
}

int sol() {
    queue<piece> Q;
    // 初始转态
    piece pe(0, 0, 0, 0);
    vis[0][0][0] = 1;
    Q.push(pe);
    
    while (!Q.empty()) {
        piece tmp = Q.front();
        Q.pop();
        int tp = tmp.p, tx = tmp.x, ty = tmp.y, steps = tmp.steps;
        if (tx == m - 1 && ty == n - 1) return steps;
        int k;
        if (tp == 0) k = 4;     // 兵
        else k = 8;             // 马
        
        // 若当前单元格为驿站
        if (mp[tx][ty] == 'S') {
            int mp = (tp + 1) % 2;
            if (!vis[tx][ty][mp]) {
                piece p(mp, tx, ty, steps + 1);
                Q.push(p);
                vis[tx][ty][mp] = 1;
            }
        }

        int np = tp, nx, ny, nsteps;
        for (int i = 0; i < k; ++i) {
            if (tp == 0) {
                nx = tx + bx[i]; ny = ty + by[i];
            } else {
                nx = tx + mx[i]; ny = ty + my[i];
            }
            nsteps = steps + 1;
            if (nx < m && nx >= 0 && ny < n && ny >= 0 && !vis[nx][ny][np] && mp[nx][ny] != 'X') {
                Q.push(piece(np, nx, ny, nsteps));
                vis[nx][ny][np] = 1;
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();

    cin >> m >> n;
    string str;
    for (int i = 0; i < m; ++i) {
        cin >> str;
        int len = str.size();
        for (int j = 0; j < len; ++j) mp[i][j] = str[j];
    }
    int ans = sol();
    cout << ans << '\n';
}
/*
9 9
.........
.....XXX.
.....X.X.
.....X.X.
.....X.XS
XXXXXX.XX
.........
.........
.........

3 2
S.
..
..
*/