文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

你現(xiàn)在很餓，想要盡快找東西吃。你需要找到最短的路徑到達(dá)一個(gè)食物所在的格子。

給定一個(gè) m x n 的字符矩陣 grid ，包含下列不同類型的格子：

'*' 是你的位置。矩陣中有且只有一個(gè) '*' 格子。 '#' 是食物。矩陣中可能存在多個(gè)食物。 '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 解釋: 這里有多個(gè)食物。拿到下邊的食物僅需走 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 中有且只有一個(gè) '*' 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-path-to-get-food
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 廣度優(yōu)先搜索

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'; // 標(biāo)記為訪問過了}}}step++;}return -1;} };

56 ms 16.8 MB C++

---

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

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1730. 获取食物的最短路径（BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。