CodeBear OJ青少年编程思维训练平台

// 四个方向：右下左上

const int dx[] = {0, 1, 0, -1};

const int dy[] = {1, 0, -1, 0};

bool dfs(int x, int y) {

    // 检查是否到达终点

    if (maze[x][y] == 3) {

        path.push_back({x, y});

        return true;  // 找到了！

    }

    // 标记当前位置已访问

    visited[x][y] = true;

    path.push_back({x, y});

    // 尝试四个方向

    for (int i = 0; i < 4; i++) {

        int nx = x + dx[i];

        int ny = y + dy[i];

        // 边界检查

        if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5

            && !visited[nx][ny] && maze[nx][ny] != 1) {

            if (dfs(nx, ny)) {

                return true;  // 找到路径

            }

        }

    }

    // 回溯：撤销选择

    path.pop_back();

    visited[x][y] = false;

    return false;

}