数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的墙壁和大门
假设我们有一个 m x n 的二维网格，它被初始化为以下三个可能的值。
-1 代表墙壁或障碍物。
0 代表大门。
INF 这表示无限大，意味着一个空房间。
这里 2^31 - 1 = 2147483647 被视为 INF，因为我们可以假设到门的距离小于 2147483647。用每个空房间到最近大门的距离填充每个空房间。如果无法到达大门，则应将其填充为 INF。
因此，如果输入类似于
| INF | -1 | 0 | INF |
| INF | INF | INF | -1 |
| INF | -1 | INF | -1 |
| 0 | -1 | INF | INF |
那么输出将是
| 3 | -1 | 0 | 1 |
| 2 | 2 | 1 | -1 |
| 1 | -1 | 2 | -1 |
| 0 | -1 | 3 | 4 |
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为 4 x 2 的数组 dir：={{1, 0}, {-1, 0}, {0, 1}, {0,-1}}
n := 房间的数量
m := （如果 n 不为零，则为列数，否则为 0）
定义一个包含对的队列 q
用于初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
用于初始化 j := 0，当 j < m 时，更新（j 加 1），执行：
如果 rooms[i, j] 等于 0，则：
将 { i, j } 插入到 q 中
用于初始化 lvl := 1，当 q 不为空时，更新（lvl 加 1），执行：
sz := q 的大小
当 sz 不为零时，在每次迭代中将 sz 减 1，执行：
定义一个对 curr := q 的第一个元素
从 q 中删除元素
x := curr.first
y := curr.second
用于初始化 i := 0，当 i < 4 时，更新（i 加 1），执行：
nx := x + dir[i, 0]
ny := y + dir[i, 1]
如果 nx < 0 或 ny < 0 或 nx >= n 或 ny >= m 或 rooms[nx, ny] < lvl，则：
忽略以下部分，跳过到下一次迭代
rooms[nx, ny] := lvl
将 { nx, ny } 插入到 q 中
示例
让我们看看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto< > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
void wallsAndGates(vector<vector<int<>& rooms) {
int n = rooms.size();
int m = n ? rooms[0].size() : 0;
queue<pair<int, int> > q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (rooms[i][j] == 0)
q.push({ i, j });
}
}
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
pair<int, int> curr = q.front();
q.pop();
int x = curr.first;
int y = curr.second;
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl)
continue;
rooms[nx][ny] = lvl;
q.push({ nx, ny });
}
}
}
}
};
main(){
vector<vector<int<> v = {{2147483647,-1,0,2147483647}, {2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1}, {0,-1,2147483647,2147483647}};
Solution ob;
ob.wallsAndGates(v);
print_vector(v);
}输入
{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}输出
[[3, -1, 0, 1, ],[2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4, ],]
454 次查看
