首页 > 试题广场 >

迷宫难题

[编程题]迷宫难题

热度指数：582 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

图森未来的自动驾驶小卡车今天被派到了一个陌生的迷宫内部运输一些货物。

工程师小图已经提前拿到了这个迷宫的地图，地图是一个n*m的字符矩阵，上面包含四种不同的字符："."，"#"，"S"和"E"。其中"S"和"E"分别代表运货的起点和终点，"."为可行驶区域，"#"为不可行驶区域。每个可行驶区域都可以移动到上、下、左、右相邻的可行驶区域，且四种移动的距离都为1。

为了估算运输的成本，小图希望你可以帮助他计算从起点到终点的最短行驶距离。

例如，对于下方的输入样例1，从起点到终点有且仅有一条路径，路径的长度为15（最开始卡车在S的位置，需要经过15次移动才能到达E的位置）。所以，最短行驶距离也为15。

而输入样例2，因为多出了一条直接从S到E的路径，所以最短行驶距离会减少到7。

输入描述:

第一行有两个正整数，分别为n和m（2 <= n, m <= 1000），为数据的行数和列数。

接下来的n行，每行包含m个字符，构成了整张地图。地图中只包含"."，"#"，"S"和"E"四种字符，且"S"和"E"都会且仅会出现一次。

输出描述:

输出一个正整数，为从起点到终点最短行驶距离的长度。

示例1

输入

6 10
##########
#........#
#.######.#
#.######.#
#.######.#
#S######E#

输出

示例2

输入

6 10
##########
#........#
#.######.#
#.######.#
#.######.#
#S......E#

输出

备注:

无论何时，卡车都不能开出地图外。
卡车一开始就停在S的位置，最短行驶距离的长度为卡车停到E时的最少移动次数。
保证至少有一条从S到E的可行路径。

算法知识视频讲解

C/C++

牛客438614504号

#include<iostream>
#include<queue>
#include<vector>
#include<string>
using namespace std;
struct Node
{
    int x;
    int y;
    int step;
}S, E, node;

int row, colum;
int cx[] = { 0,0,-1,1 };
int cy[] = { 1,-1,0,0 };

bool judge(int x, int y, vector<vector<bool>> &visit, vector<vector<char>> &martix)
{
    if (x < 0 || x >= row || y < 0 || y >= colum)
    {
        return false;
    }

    if (visit[x][y] || martix[x][y] == '#')
    {
        return false;
    }

    return true;
}

//从起点S开始进行广度优先遍历(BFS)
int BFS(vector<vector<bool>> &visit,vector<vector<char>> &martix)
{
    queue<Node> MyQueue;//辅助队列，用于存储遍历过程中遇到的点；
    S.step = 0;
    MyQueue.push(S);
    visit[S.x][S.y] = true;
    while (!MyQueue.empty())
    {
        Node top = MyQueue.front();
        MyQueue.pop();
        if (top.x == E.x && top.y == E.y)
        {
            return top.step;
        }

        for (int i = 0; i < 4; i++)
        {
            int tempx = top.x + cx[i];
            int tempy = top.y + cy[i];
            if (judge(tempx, tempy,visit,martix))
            {
                node.x = tempx;
                node.y = tempy;
                node.step = top.step + 1;
                MyQueue.push(node);
                visit[tempx][tempy] = true;
            }
        }
    }

    return -1;
}

void getmartix(vector<vector<char>> &martix)
{

    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < colum; j++)
        {
            cin >> martix[i][j];
            if (martix[i][j] == 'S')
            {
                S.x = i;
                S.y = j;
            }
            if (martix[i][j] == 'E')
            {
                E.x = i;
                E.y = j;
            }
        }
    }

}

int main()
{

    cin >> row >> colum;
    vector<vector<char>> martix(row, vector<char>(colum));
    vector<vector<bool>> visit(row, vector<bool>(colum));
    getmartix(martix);
    cout << BFS(visit,martix);
    return 0;
}

发表于 2021-04-26 14:06:28 回复(0)

nevva

C++的dfs和bfs双解，dfs是超时的。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
private:
    int n, m;
    int sx, sy;
    int ex, ey;
    vector<vector<char>>& map;
    vector<vector<int>> path;
    vector<int> dx{-1, 0, 0, 1};
    vector<int> dy{0, -1, 1, 0};

public:
    Solution(vector<vector<char>>& map_, int n_, int m_, int sx_, int sy_, int ex_, int ey_) : map(map_), n(n_), m(m_), sx(sx_), sy(sy_), ex(ex_), ey(ey_) {
        path = vector<vector<int>>(n, vector<int>(m, INT32_MAX));
        path[sx][sy] = 0;
    }

    int dfs() {
        dfs(sx, sy);
        return path[ex][ey];
    }

    void dfs(int ox, int oy) {
        for (int i = 0; i < 4; i++) {
            int x = ox + dx[i];
            int y = oy + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == '#') {
                continue;
            }
            if (path[ox][oy] + 1 < path[x][y]) {
                path[x][y] = path[ox][oy] + 1;
                if (x == ex && y == ey) {
                    continue;
                }
                dfs(x, y);
            }
        }
    }

    int bfs() {
        queue<vector<int>> q;
        q.push({sx, sy});

        while (!q.empty()) {
            int ox = q.front()[0];
            int oy = q.front()[1];
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = ox + dx[i];
                int y = oy + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == '#' || path[x][y] != INT32_MAX) {
                    continue;
                }
                path[x][y] = path[ox][oy] + 1;
                if (x == ex && y == ey) {
                    return path[ex][ey];
                }
                q.push({x, y});
            }
        }
        return -1;
    }
};

int main() {
    int n, m;
    int sx, sy;
    int ex, ey;
    cin >> n;
    cin >> m;
    vector<vector<char>> map(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char t;
            cin >> t;
            if (t == 'S') {
                sx = i;
                sy = j;
            } else if (t == 'E') {
                ex = i;
                ey = j;
            }
            map[i][j] = t;
        }
    }
    Solution solution(map, n, m, sx, sy, ex, ey);
    cout << solution.bfs() << endl;
    //cout << solution.dfs() << endl;
    return 0;
}

发表于 2022-10-17 21:22:57 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        in.nextLine();
        String[] board = new String[n];
        for (int i = 0; i < n; i++) {
            String s = in.nextLine();
            board[i] = s;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i].charAt(j) == 'S') {
                    int res = fun(board, i, j);
                    System.out.println(res);
                    break;
                }
            }
        }
    }
    //  bfs处理
    static int[][] d = new int[][]{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    public static int fun(String[] board, int x, int y) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        int n = board.length, m = board[0].length();
        boolean[][] v = new boolean[n][m]; // 是否访问过
        q.offer(new int[]{x, y});
        v[x][y] = true;
        int cnt = 0;
        while (!q.isEmpty()) {
            int len = q.size();
            for (int i = 0; i < len; i++) {
                int[] cp = q.poll();
                int a = cp[0], b = cp[1];
                for (int j = 0; j < 4; j++) {
                    int ni = a + d[j][0], nj = b + d[j][1];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m) { 
                        if (board[ni].charAt(nj) == 'E') return cnt+1; // 到达终点直接返回
                        if (!v[ni][nj] && board[ni].charAt(nj) == '.') {// 可行
                            v[ni][nj] = true;
                            q.offer(new int[]{ni, nj});
                        }
                    }
                }
            }
            cnt++;
        }
        return -1;
    }
}

发表于 2022-06-27 13:20:52 回复(0)

317102060740王逸伦

#include<iostream>
#include<string>
using namespace std;
bool vis[1000][1000];
int n,m;
string maze[1000];
int ans=100000;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool in(int x,int y){
    return x>=0&&x<n&&y>=0&&y<m;
}
void dfs(int x,int y,int step){
     vis[x][y]=1;
    if(maze[x][y]=='E'){
        if(step<ans){
            ans=step;
        }
    }
    for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(in(tx,ty)&&maze[tx][ty]!='#'&&!vis[tx][ty]){
            dfs(tx,ty,step+1);
        }
    }
    vis[x][y]=0;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>maze[i];
    }
    int x,y;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maze[i][j]=='S'){
                x=i,y=j;
            }
        }
    }
    dfs(x,y,0);
    cout<<ans;
    return 0;
}

发表于 2019-12-12 19:55:04 回复(0)

提交观点

问题信息

C++工程师 iOS工程师图森未来安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师 c#工程师 2020 大数据开发工程师 Java工程师

上传者：小小

难度：

4条回答 22收藏 4074浏览

通过挑战的用户

想在家办公的鳄...

2022-11-14 00:15:56
牛客66995...

2022-10-31 14:58:00
牛客54464...

2022-10-20 17:36:35
nevva

2022-10-17 21:16:09
联想校招内推

2022-09-26 14:14:38

迷宫难题

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题