文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 BFS 超時(shí)解
    • 2.2 從門開始逆向BFS

1. 題目

你被給定一個(gè) m × n 的二維網(wǎng)格，網(wǎng)格中有以下三種可能的初始化值：

• -1 表示墻或是障礙物
• 0 表示一扇門
• INF 無限表示一個(gè)空的房間。然后，我們用 231 - 1 = 2147483647 代表 INF。你可以認(rèn)為通往門的距離總是小于 2147483647 的。

你要給每個(gè)空房間位上填上該房間到 最近 門的距離，如果無法到達(dá)門，則填 INF 即可。

示例： 給定二維網(wǎng)格： INF -1 0 INF INF INF INF -1 INF -1 INF -10 -1 INF INF 運(yùn)行完你的函數(shù)后，該網(wǎng)格應(yīng)該變成：3 -1 0 12 2 1 -11 -1 2 -10 -1 3 4

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

2. 解題

2.1 BFS 超時(shí)解

• 對(duì)每個(gè)點(diǎn)進(jìn)行BFS，超時(shí)

class Solution { public:void wallsAndGates(vector<vector<int>>& rooms) {if(rooms.size()==0 || rooms[0].size()==0) return;int INF = INT_MAX, i, j, k,step,size,x,y,nx,ny;int m = rooms.size(), n = rooms[0].size();vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(rooms[i][j]!=INF)continue;vector<vector<bool>> visited(m, vector<bool>(n,false));visited[i][j] = true;queue<vector<int>> q;q.push({i,j});step = 0;bool found = false;while(!q.empty()){size = q.size();while(size--){x = q.front()[0];y = q.front()[1];q.pop();if(rooms[x][y]==0){rooms[i][j] = step;found = true;break;}for(k = 0; k < 4; ++k){nx = x + dir[k][0];ny = y + dir[k][1];if(nx>=0 && nx<m && ny>=0 && ny<n && !visited[nx][ny] && rooms[nx][ny] != -1){q.push({nx,ny});visited[nx][ny] = true;}}}if(found)break;step++;}}}} };

2.2 從門開始逆向BFS

• 對(duì)所有的門同時(shí)進(jìn)行BFS，逆向考慮，每個(gè)位置最多訪問一次

class Solution { public:void wallsAndGates(vector<vector<int>>& rooms) {if(rooms.size()==0 || rooms[0].size()==0) return;int INF = INT_MAX, i, j, k,step = 0,size,x,y,nx,ny;int m = rooms.size(), n = rooms[0].size();vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};vector<vector<bool>> visited(m, vector<bool>(n,false)); queue<vector<int>> q;for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(rooms[i][j]==0){visited[i][j] = true;q.push({i,j});}}}while(!q.empty()){ size = q.size();while(size--){x = q.front()[0];y = q.front()[1];q.pop();if(rooms[x][y]==INF){rooms[x][y] = step;}for(k = 0; k < 4; ++k){nx = x + dir[k][0];ny = y + dir[k][1];if(nx>=0 && nx<m && ny>=0 && ny<n && !visited[nx][ny] && rooms[nx][ny] != -1){q.push({nx,ny});visited[nx][ny] = true;}}}step++;}} };

124 ms 18.8 MB

---

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)，一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 286. 墙与门（BFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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