首页 > 试题广场 >

迷宫中的牛可乐

[编程题]迷宫中的牛可乐
  • 热度指数：132 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛可乐有一个行列的迷宫，如果是'#',代表第行第列的方格为墙壁，如果是'.',代表第行第列的方格为可走方格。

每一步移动在一个可走方格，可以水平的或者垂直的移动到相邻的一个可走方格中。

但是不能走出迷宫，不能走到一个墙壁方格，也不能对角线方向移动。

你可以选择任意一个起点方格和终点方格（这两个方格必须为可走方格，且可以相互到达）。

牛可乐将从你选择的起点方格用最小的步数移动到终点方格。

本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大，你需要计算这个步数的最大值。


输入描述:
第一行一个整数
接下来行，每行个字符 代表迷宫
中至少包含2个字符‘.’


输出描述:
一行一个整数代表答案
示例1

输入

3 3
...
.#.
...

输出

4
示例2

输入

5 5
...#.
...#.
.#...
#....
.#..#

输出

8
示例3

输入

5 5
#..#.
...#.
.....
#.#..
....#

输出

8
算法知识视频讲解
添加回答
pein531头像 pein531
遍历所有的“起点”可能性，针对每个“起点”进行宽度优先搜索，计算离所有可到达“终点”的步数，选择出其中最大的步数即可。不过这种题目，真心运行得慢，python几乎都超时，还是得Java或者C++。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.ArrayDeque;

public class Main {
    // 要求的最大步数
    static int maxSteps = 0;
    // 四个方向的坐标变化
    static int[][] orientation = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    // 迷宫行数和列数
    static int n, m;
    // 迷宫矩阵
    static char[][] grid;
    // 动规矩阵
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strNM = br.readLine().trim().split(" ");
        n = Integer.parseInt(strNM[0]);
        m = Integer.parseInt(strNM[1]);
        grid = new char[n][m];
        for(int i = 0; i < n; i++){
            char[] row = br.readLine().trim().toCharArray();
            for(int j = 0; j < m; j++) grid[i][j] = row[j];
        }
        // 遍历所有坐标，对可能的起点进行宽搜
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == '.'){
                    dp = new int[n][m];    // 对于每个起点，都需要新的dp
                    bfs(i, j);
                }
            }
        }
        System.out.println(maxSteps);
    }
    
    private static void bfs(int startX, int startY) {
        Queue<int[]> queue = new ArrayDeque();
        queue.offer(new int[]{startX, startY});
        // dp还需要一位来表示该坐标是否被访问过，0表示未被访问过
        dp[startX][startY] = 1;
        // 各种尝试，计算走到能达到的终点需要多少步
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            // 取出队首的坐标，然后对能走的四个方向进行尝试
            for(int i = 0; i < 4; i++){
                int endX = point[0] + orientation[i][0];
                int endY = point[1] + orientation[i][1];
                // 如果终点位置合法且没有被访问过，则更新一下步数
                if(endX >= 0 && endX < n &&
                   endY >= 0 && endY < m &&
                   grid[endX][endY] != '#' &&
                   dp[endX][endY] == 0){
                    dp[endX][endY] = dp[point[0]][point[1]] + 1;
                    queue.offer(new int[]{endX, endY});
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // 由于用0来表示未访问了，因此距离要减1
                maxSteps = Math.max(maxSteps, dp[i][j] - 1);
            }
        }
    }
}


编辑于 2021-01-23 14:27:27 回复(0)
Dem1an头像 Dem1an 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
  
int main(){
    int r,c;
    cin>>r>>c;
    vector<vector<char>> quiz(r, vector<char> (c));
    vector<vector<bool>> visit(r, vector<bool> (c,false));
    for(int i=0;i<r;++i){
        for(int j=0;j<c;++j){
            cin>>quiz[i][j];
            if(quiz[i][j]=='#'){
                visit[i][j]=true;
            }
        }
    }
    int maxcnt = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (quiz[i][j] == '#') {
                continue;
            } else {
                queue<pair<int, int>> que;
                que.push({i, j});
                vector<vector<bool>> tmp(visit);
                tmp[i][j] = true;
                int cnt = 0;
                while (!que.empty()) {
                    int sz = que.size();
                    for (int i = 0; i < sz; ++i) {
                        pair<int, int> pr = que.front();
                        que.pop();
                        if (pr.first - 1 >= 0 &&
                            !tmp[pr.first - 1][pr.second]) {
                            que.push({pr.first - 1, pr.second});
                            tmp[pr.first - 1][pr.second] = true;
                        }
                        if (pr.first + 1 < quiz.size() &&
                            !tmp[pr.first + 1][pr.second]) {
                            que.push({pr.first + 1, pr.second});
                            tmp[pr.first + 1][pr.second] = true;
                        }
                        if (pr.second - 1 >= 0 &&
                            !tmp[pr.first][pr.second - 1]) {
                            que.push({pr.first, pr.second - 1});
                            tmp[pr.first][pr.second - 1] = true;
                        }
                        if (pr.second + 1 < quiz[0].size() &&
                            !tmp[pr.first][pr.second + 1]) {
                            que.push({pr.first, pr.second + 1});
                            tmp[pr.first][pr.second + 1] = true;
                        }
                    }
                    ++cnt;
                }
                --cnt;
                maxcnt = max(maxcnt, cnt);
            }
        }
    }
    cout << maxcnt << endl;
  
      
    return 0;
}
广度优先搜索。
发表于 2022-03-05 12:01:03 回复(0)
提交观点

问题信息

贝壳找房 算法工程师 2021
来自：贝壳找房2021届校招...
上传者：小小
难度：
2条回答 1938浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号