LeetCode 1730. 获取食物的最短路径（BFS）

Michael阿明

发布于 2021-09-06 11:37:29

7060

发布于 2021-09-06 11:37:29

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

你现在很饿，想要尽快找东西吃。你需要找到最短的路径到达一个食物所在的格子。

给定一个 m x n 的字符矩阵 grid ，包含下列不同类型的格子：

'*' 是你的位置。矩阵中有且只有一个 '*' 格子。
'#' 是食物。矩阵中可能存在多个食物。
'O' 是空地，你可以穿过这些格子。
'X' 是障碍，你不可以穿过这些格子。

返回你到任意食物的最短路径的长度。如果不存在你到任意食物的路径，返回 -1。

示例 1:

输入： grid = [
["X","X","X","X","X","X"],
["X","*","O","O","O","X"],
["X","O","O","#","O","X"],
["X","X","X","X","X","X"]]
输出： 3
解释： 要拿到食物，你需要走 3 步。

Example 2:

输入： grid = [
["X","X","X","X","X"],
["X","*","X","O","X"],
["X","O","X","#","X"],
["X","X","X","X","X"]]
输出： -1
解释： 你不可能拿到食物。

示例 3:

输入: grid = [
["X","X","X","X","X","X","X","X"],
["X","*","O","X","O","#","O","X"],
["X","O","O","X","O","O","X","X"],
["X","O","O","O","O","#","O","X"],
["X","X","X","X","X","X","X","X"]]
输出: 6
解释: 这里有多个食物。拿到下边的食物仅需走 6 步。

示例 4:
输入: grid = [["O","*"],["#","O"]]
输出: 2

示例 5:
输入: grid = [["X","*"],["#","X"]]
输出: -1
 
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[row][col] 是 '*'、 'X'、 'O' 或 '#' 。
grid 中有且只有一个 '*' 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/shortest-path-to-get-food 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

广度优先搜索

class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
        queue<int> q;
        bool found = false;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
                if(grid[i][j] == '*')
                {
                    q.push(i*256+j);
                    grid[i][j] = 'X'; // 访问过了
                    found = true;
                    break;
                }
            if(found)
                break;
        }
        int step = 0;
        while(!q.empty())
        {
            int size = q.size();
            while(size--)
            {
                int x = q.front()/256;
                int y = q.front()%256;
                if(grid[x][y]=='#') //食物
                    return step;
                q.pop();
                for(int d = 0; d < 4; ++d)
                {
                    int nx = x + dir[d][0];
                    int ny = y + dir[d][1];
                    if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny]!='X')
                    {
                        q.push(nx*256+ny);
                        if(grid[nx][ny] != '#')
                            grid[nx][ny] = 'X'; // 标记为访问过了
                    }
                }
            }
            step++;
        }
        return -1;
    }
};

56 ms 16.8 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https