HJ43 迷宫问题

发表于 分类于 ， 阅读次数： Waline： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

#HJ43 迷宫问题

描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

1
2
3
4
5
6
7
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围： 2≤n,m≤10 2≤*n*,*m*≤10， 输入的内容只包含 0≤val≤1 0≤*v**a**l*≤1

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

示例：

输入：

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出：

(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

思路：

dfs直接输出即可。使用pair来记录路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

int n,m;
int maze[10][10];
//记录路径
int vis[10][10];
vector<pair<int, int> >mp;
//上，下，左，右
int dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}};

void dfs(int x, int y){
    //base case
    if(x == n - 1 && y == m - 1){
        //输出，要不然会回退
        for(int i = 0; i < mp.size(); i++){
            cout << "(" << mp[i].first << "," << mp[i].second << ")" << endl;
        }
        return;
    }else{
        for(int i = 0;i < 4; i++){
            //寻找方向
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            
            if(dx >= 0 && dx < n && dy >= 0 && dy < m && vis[dx][dy] == 0 && maze[dx][dy] == 0){
                //标记走过
                vis[dx][dy] = 1;
                mp.push_back(make_pair(dx, dy));
                dfs(dx,dy);
              	//回退
                vis[dx][dy] = 0;
                mp.pop_back();
            }
        }
    }
}

int main(){
    memset(vis, 0, sizeof(vis));
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> maze[i][j];
        }
    }
    mp.push_back(make_pair(0, 0));
    vis[0][0] = 1;
    dfs(0, 0);
    return 0;
}