中国象棋（马）

xiufanivan · 2023-03-04 22:17:35 · 个人记录

题目描述： 中国象棋博大精深，其中马的规则最为复杂，也是最难操控的一颗棋子。我们都知道象棋中马走“日“，比如在(2,4)位置的一个马，跳一步能到达的位置有(0,3)，(0,5)，(1,2)，(1,6)，(3,2)，(3,6)，(4,3)，(4,5)。

蒜头君正在和花椰妹下棋，蒜头君正在进行战略布局，他需要把在(x,y)位置的马跳到(x',y')位置以达到威慑的目的。 但是棋盘大小有限制，棋盘是一个10×9的网格，左上角坐标为(0,0)，右下角坐标为(9,8)，马不能走出棋盘，并且有些地方已经有了棋子，马也不能跳到有棋子的点。

蒜头君想知道，在不移动其他棋子的情况下，能否完成他的战略目标。

输入格式：

输入一共10行，每行一个长度为9的字符串。输入表示这个棋盘，我们用 '·' 表示空位置，用'#'表示该位置有棋子，用·S'表示初始的马的位置，用'T'表示马需要跳到的位置。输入保证一定只存在一个'S'和一个'T'。

输出格式：

如果在不移动其他棋子的情况下，马能从'S'跳到'T',那么输出一行"Yes”,否则输出一行"No”。

样例输入：

.#....#S#
..#.#.#..
..##.#..#
......##.
...T.....
...#.#...
...#.....
...###...
.........
.##......

样例输出：

Yes

代码：

#include <bits/stdc++.h>
using namespace std;

string s[10];  // 存储棋盘 
bool f = false;  // 是否抵达终点 
bool vis[10][9];  // 是否走过
int dir[8][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}; 

// 判断在棋盘内
bool in(int x, int y) {
    return x >=0 && x < 10 && y >= 0 && y < 9;
} 

void backtrack(int x, int y) {
    vis[x][y] = true;
    if (f == true) {
        return;
    }
    if (s[x][y] == 'T') {
        f = true;
        return;
    }
    for (int i = 0; i < 8; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && s[tx][ty] != '#' && !vis[tx][ty]) {
            backtrack(tx, ty);
        }
    }
}

int main() {
    int sx, sy;  // 起点坐标 
    // 输入棋盘 
    for (int i = 0; i < 10; i++) {
        cin >> s[i];
    }
    // 初始化vis
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 9; j++) {
            vis[i][j] = false;
        }
    } 
    // 找起点坐标
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 9; j++) {
            if (s[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    } 
    backtrack(ex, ey);
    // 输出答案 
    if (f == true) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}