牛郎织女迷宫问题c++

牛郎织女迷宫问题是一个经典的搜索问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

以下是使用C++语言实现DFS的代码：

#include<iostream>
using namespace std;

const int N = 10;  // 最大迷宫大小
int n, m;  // 迷宫大小
int sx, sy, ex, ey;  // 起点和终点坐标
int maze[N][N];  // 迷宫数组
bool st[N][N];  // 标记数组

// 搜索函数
bool dfs(int x, int y) {
    // 如果到达终点，返回true
    if (x == ex && y == ey) return true;

    // 标记当前位置已经访问过
    st[x][y] = true;

    // 枚举四个方向
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        // 判断新位置是否越界或者已经访问过
        if (a < 0 || a >= n || b < 0 || b >= m || maze[a][b] || st[a][b]) continue;
        // 递归搜索
        if (dfs(a, b)) return true;
    }

    // 没有找到路径，返回false
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }
    cin >> sx >> sy >> ex >> ey;

    if (dfs(sx, sy)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

输入格式：

第一行包含两个正整数n和m，表示迷宫的大小。

接下来n行，每行m个整数，表示迷宫的布局，0表示可以通过，1表示障碍物。

最后一行包含四个正整数，分别表示起点和终点的坐标。

输出格式：

如果存在通路，输出"Yes"，否则输出"No"。

样例输入：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
0 0 4 3

样例输出：

Yes