走迷宫

· · 个人记录

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

输入格式： 第1行是一个正整数n(1<=n<=100),表示迷宫的规模是n*n的。接下来是一个n*n的矩阵，矩阵中的元素为 . 或者 # 。再接下来一行是4个整数ha,la,hb,lb,描述A处在第ha行，第la列，B处在第hb行，第lb列。注意到ha,la,hb,lb全部是从0开始计数的。

输出格式： 能办到则输出“YES”,否则输出“NO”。

样例输入：

3
. # #
. # #
. . .
0 0 2 2

样例输出：

YES

代码1（DFS）： 

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

char mp[100][100];  // 存储迷宫地区
bool vis[100][100] = {false};  // 记录是否走过，初始为false，走过记为true
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};  // 方向数组 
int n, sx, sy, ex, ey; // 地图尺寸，起点、终点坐标 
bool f = false;

// 判断坐标在不在地图范围内
bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
} 

// 走迷宫dfs递归函数
void dfs(int x, int y) {
    // 若到达终点，退出 
    if (x == ex && y == ey) {
        f = true;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        // 条件为：在地图内，路未走过，路可以走
        // 必须先判断在不在地图内，不然vis[tx][ty]可能会发生数组越界
        if (in(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty]) {
            vis[x][y] = true;
            dfs(tx, ty);
            vis[x][y] = false;
        }
    }
}

int main()
{
    // 输入地图尺寸 
    cin >> n;

    // 输入迷宫地图 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mp[i][j];
        }
    }

    // 输入起点、终点坐标
    cin >> sx >> sy >> ex >> ey;

    // 若起点或终点为 # ，则输出no
    if (mp[sx][sy] == '#' || mp[ex][ey] == '#') {
        cout << "NO" << endl;
    } else {
        // 搜索，走迷宫
        dfs(sx, sy);
        // 判断是否到达
        if (f == true) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

代码2（BFS）：

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

char mp[100][100];  // 存储迷宫地区
bool vis[100][100] = {false};  // 记录是否走过，初始为false，走过记为true
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};  // 方向数组 
int n, sx, sy, ex, ey; // 地图尺寸，起点、终点坐标
bool f = false;

// 迷宫结点结构体 
struct Node {
    int x, y, step;
    Node(int x, int y, int step) {
        this->x = x;
        this->y = y;
        this->step = step;
    }
};

// 判断坐标在不在地图范围内
bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n; 
}

// 走迷宫bfs函数
void bfs() {
    queue<Node> q;
    // 起点加入队列 
    q.push(Node(sx, sy, 0));
    // 标记起点访问 
    vis[sx][sy] = true;

    while (!q.empty()) {
        // 访问队列中队首元素now
        Node now = q.front();
        // 删除队首元素
        q.pop();

        for (int i = 0; i < 4; i++) {
            int tx = now.x + dir[i][0];
            int ty = now.y + dir[i][1];
            // 该点未被访问过且合法
            if (in(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty]) {
                // 若到终点 
                if (tx == ex && ty == ey) {
                    f = true;
                    return;
                } else {
                    // 将该点加入队列末尾
                    q.push(Node(tx, ty, now.step + 1));
                    vis[tx][ty] = true;
                }
            }
        }
    }
}

int main()
{
    // 输入地图尺寸 
    cin >> n;

    // 输入迷宫地图 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mp[i][j];
        }
    }

    // 输入起点、终点坐标
    cin >> sx >> sy >> ex >> ey;

    // 若起点或终点为 # ，则输出no
    if (mp[sx][sy] == '#' || mp[ex][ey] == '#') {
        cout << "NO" << endl;
    } else {
        bfs(); 
        // 判断是否到达
        if (f == true) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}