K11541 迷宫 题目描述 小科森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，“.”和"#"，"."前者表示可以通行,"#"表示不能通行。同时当小科处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，小科想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。c++

这是一个典型的图论问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。我们可以将迷宫看作是一个由点和边组成的图，每个点表示迷宫中的一个格子，每条边表示相邻的两个格子之间可以通行。

由于题目中只有两种状态，我们可以使用邻接矩阵来表示这个图。邻接矩阵中的每个元素表示相邻的两个格子之间是否可以通行。如果可以通行，则为1，否则为0。

下面是一个基于邻接矩阵的DFS实现示例：

#include <iostream>
using namespace std;

const int MAXN = 105;
int n;
char maze[MAXN][MAXN];
int graph[MAXN * MAXN][MAXN * MAXN];
bool visited[MAXN * MAXN];

// 将迷宫转换成邻接矩阵
void buildGraph() {
    int idx = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (maze[i][j] == '.') {
                idx = (i - 1) * n + j;
                if (maze[i + 1][j] == '.') {
                    graph[idx][idx + n] = 1;
                    graph[idx + n][idx] = 1;
                }
                if (maze[i][j + 1] == '.') {
                    graph[idx][idx + 1] = 1;
                    graph[idx + 1][idx] = 1;
                }
            }
        }
    }
}

// DFS搜索
bool dfs(int cur, int dest) {
    if (cur == dest) {
        return true;
    }
    visited[cur] = true;
    for (int i = 1; i <= n * n; i++) {
        if (graph[cur][i] && !visited[i]) {
            if (dfs(i, dest)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> maze[i][j];
        }
    }
    if (maze[1][1] == '#' || maze[n][n] == '#') {
        cout << "No" << endl;
    } else {
        // 构建邻接矩阵
        buildGraph();
        // DFS搜索
        if (dfs(1, n * n)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

在上面的代码中，我们首先读入n和迷宫的状态，然后判断起点和终点是否可以通行。如果有一个不能通行，则输出"No"。否则，我们先将迷宫转换成邻接矩阵，接着使用DFS进行搜索。

注意，由于小科只能移动到东南西北四个方向之一的相邻格点上，因此我们只需要考虑相邻的两个格子之间是否可以通行，而不需要考虑跨越多个格子的情况。