未来的门户网站,网站仿做,广州seo推荐,免费表白网页在线生成制作文章目录1. 题目2. 解题1. 题目
你现在很饿#xff0c;想要尽快找东西吃。你需要找到最短的路径到达一个食物所在的格子。
给定一个 m x n 的字符矩阵 grid #xff0c;包含下列不同类型的格子#xff1a;
* 是你的位置。矩阵中有且只有一个 * 格子。
# 是食物。矩阵中可…
文章目录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(vectorvectorchar grid) {int m grid.size(), n grid[0].size();vectorvectorint dir {{1,0},{0,1},{-1,0},{0,-1}};queueint 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*256j);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(nx0 nxm ny0 nyn grid[nx][ny]!X){q.push(nx*256ny);if(grid[nx][ny] ! #)grid[nx][ny] X; // 标记为访问过了}}}step;}return -1;}
};56 ms 16.8 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
