创意专业网站建设,国际贸易网站建设 中企动力湖北,中国品牌加盟网,百度收录网站中文称文章目录1. 题目2. 解题2.1 BFS 超时解2.2 从门开始逆向BFS1. 题目
你被给定一个 m n 的二维网格#xff0c;网格中有以下三种可能的初始化值#xff1a;
-1 表示墙或是障碍物0 表示一扇门INF 无限表示一个空的房间。然后#xff0c;我们用 231 - 1 2147483647 代表 INF…
文章目录1. 题目2. 解题2.1 BFS 超时解2.2 从门开始逆向BFS1. 题目
你被给定一个 m × n 的二维网格网格中有以下三种可能的初始化值
-1 表示墙或是障碍物0 表示一扇门INF 无限表示一个空的房间。然后我们用 231 - 1 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。
你要给每个空房间位上填上该房间到 最近 门的距离如果无法到达门则填 INF 即可。
示例
给定二维网格
INF -1 0 INF
INF INF INF -1
INF -1 INF -10 -1 INF INF
运行完你的函数后该网格应该变成3 -1 0 12 2 1 -11 -1 2 -10 -1 3 4来源力扣LeetCode 链接https://leetcode-cn.com/problems/walls-and-gates 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 BFS 超时解
对每个点进行BFS超时
class Solution {
public:void wallsAndGates(vectorvectorint 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();vectorvectorint 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;vectorvectorbool visited(m, vectorbool(n,false));visited[i][j] true;queuevectorint 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(nx0 nxm ny0 nyn !visited[nx][ny] rooms[nx][ny] ! -1){q.push({nx,ny});visited[nx][ny] true;}}}if(found)break;step;}}}}
};2.2 从门开始逆向BFS
对所有的门同时进行BFS逆向考虑每个位置最多访问一次
class Solution {
public:void wallsAndGates(vectorvectorint 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();vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};vectorvectorbool visited(m, vectorbool(n,false)); queuevectorint 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(nx0 nxm ny0 nyn !visited[nx][ny] rooms[nx][ny] ! -1){q.push({nx,ny});visited[nx][ny] true;}}}step;}}
};124 ms 18.8 MB 长按或扫码关注我的公众号一起加油、一起学习进步
