【正经题解】Gold King勇闯八卦图

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

int rows, cols, maxSteps;
vector<vector<char>> maze;

// 深度优先搜索函数，判断从当前位置是否可以达到终点，并且步数不超过给定的步数
bool dfs(int i, int j, int steps) {
    // 如果超出边界或者当前位置为墙壁，则无法继续前进
    if (i < 0 || i >= rows || j < 0 || j >= cols || maze[i][j] == 'X') {
        return false;
    }

    // 如果当前位置为终点且步数符合要求，返回true
    if (maze[i][j] == 'T' && steps == maxSteps) {
        return true;
    }

    // 如果当前步数已经超过给定步数，返回false
    if (steps >= maxSteps) {
        return false;
    }

    // 保存当前位置的值，避免后续递归影响
    char temp = maze[i][j];
    // 将当前位置标记为已访问，避免重复访问
    maze[i][j] = 'X';

    // 递归四个方向进行深度优先搜索
    bool found = false;
    found |= dfs(i + 1, j, steps + 1); 
    found |= dfs(i - 1, j, steps + 1); 
    found |= dfs(i, j + 1, steps + 1); 
    found |= dfs(i, j - 1, steps + 1); 

    // 恢复当前位置的值，以便其他路径使用
    maze[i][j] = temp;

    return found;
}

int main() {
    int numTests;
    cin >> numTests;

    while (numTests--) {
        // 读取输入数据
        cin >> rows >> cols >> maxSteps;
        maze.resize(rows, vector<char>(cols));

        int startRow, startCol;

        // 遍历输入，找到入口位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                cin >> maze[i][j];
                if (maze[i][j] == 'S') {
                    startRow = i;
                    startCol = j;
                }
            }
        }

        // 调用深度优先搜索函数，判断是否能够走出
        if (dfs(startRow, startCol, 0)) {
            cout << "YES" << "\n";
        } else {
            cout << "NO" << "\n";
        }
    }

    return 0;
}