LeetCode 1730. 獲取食物的最短路徑(BFS)

Michael阿明 2021-08-15 22:28:25 阅读数:948

本文一共[544]字,预计阅读时长:1分钟~
leetcode 食物 最短 短路 bfs

文章目錄

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阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753150U.html