题目描述
给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid ，其中 (r, c) 表示：
- 如果
grid[r][c] = 1 ，则表示一个存在小偷的单元格 - 如果
grid[r][c] = 0 ，则表示一个空单元格
你最开始位于单元格 (0, 0) 。在一步移动中，你可以移动到矩阵中的任一相邻单元格，包括存在小偷的单元格。
矩阵中路径的 安全系数 定义为：从路径中任一单元格到矩阵中任一小偷所在单元格的 最小 曼哈顿距离。
返回所有通向单元格 (n - 1, n - 1) 的路径中的 最大安全系数 。
单元格 (r, c) 的某个 相邻 单元格，是指在矩阵中存在的 (r, c + 1)、(r, c - 1)、(r + 1, c) 和 (r - 1, c) 之一。
两个单元格 (a, b) 和 (x, y) 之间的 曼哈顿距离 等于 | a - x | + | b - y | ，其中 |val| 表示 val 的绝对值。
示例 1：
输入：grid = [[1,0,0],[0,0,0],[0,0,1]]
输出：0
解释：从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。
示例 2：
输入：grid = [[0,0,1],[0,0,0],[0,0,0]]
输出：2
解释：
上图所示路径的安全系数为 2：
- 该路径上距离小偷所在单元格（0，2）最近的单元格是（0，0）。它们之间的曼哈顿距离为 | 0 - 0 | + | 0 - 2 | = 2 。
可以证明，不存在安全系数更高的其他路径。
示例 3：
输入：grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
输出：2
解释：
上图所示路径的安全系数为 2：
- 该路径上距离小偷所在单元格（0，3）最近的单元格是（1，2）。它们之间的曼哈顿距离为 | 0 - 1 | + | 3 - 2 | = 2 。
- 该路径上距离小偷所在单元格（3，0）最近的单元格是（3，2）。它们之间的曼哈顿距离为 | 3 - 3 | + | 0 - 2 | = 2 。
可以证明，不存在安全系数更高的其他路径。
提示：
1 <= grid.length == n <= 400grid[i].length == ngrid[i][j] 为 0 或 1grid 至少存在一个小偷
解法
方法一：多源 BFS + 排序 + 并查集
我们可以先找出所有小偷的位置，然后从这些位置开始进行多源 BFS，得到每个位置到小偷的最短距离，然后按照距离从大到小排序，将每个位置逐个加入并查集，如果最终起点和终点在同一个连通分量中，那么当前距离就是答案。
时间复杂度 \(O(n^2 \times \log n)\)，空间复杂度 \(O(n^2)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return 0
q = deque()
dist = [[inf] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if grid[i][j]:
q.append((i, j))
dist[i][j] = 0
dirs = (-1, 0, 1, 0, -1)
while q:
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and dist[x][y] == inf:
dist[x][y] = dist[i][j] + 1
q.append((x, y))
q = ((dist[i][j], i, j) for i in range(n) for j in range(n))
q = sorted(q, reverse=True)
uf = UnionFind(n * n)
for d, i, j in q:
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and dist[x][y] >= d:
uf.union(i * n + j, x * n + y)
if uf.find(0) == uf.find(n * n - 1):
return int(d)
return 0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86 | class Solution {
public int maximumSafenessFactor(List<List<Integer>> grid) {
int n = grid.size();
if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {
return 0;
}
Deque<int[]> q = new ArrayDeque<>();
int[][] dist = new int[n][n];
final int inf = 1 << 30;
for (int[] d : dist) {
Arrays.fill(d, inf);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid.get(i).get(j) == 1) {
dist[i][j] = 0;
q.offer(new int[] {i, j});
}
}
}
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
int[] p = q.poll();
int i = p[0], j = p[1];
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] == inf) {
dist[x][y] = dist[i][j] + 1;
q.offer(new int[] {x, y});
}
}
}
List<int[]> t = new ArrayList<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
t.add(new int[] {dist[i][j], i, j});
}
}
t.sort((a, b) -> Integer.compare(b[0], a[0]));
UnionFind uf = new UnionFind(n * n);
for (int[] p : t) {
int d = p[0], i = p[1], j = p[2];
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= d) {
uf.union(i * n + j, x * n + y);
}
}
if (uf.find(0) == uf.find(n * n - 1)) {
return d;
}
}
return 0;
}
}
class UnionFind {
public int[] p;
public int n;
public UnionFind(int n) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
this.n = n;
}
public boolean union(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) {
return false;
}
p[pa] = pb;
--n;
return true;
}
public int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78 | class UnionFind {
public:
vector<int> p;
int n;
UnionFind(int _n)
: n(_n)
, p(_n) {
iota(p.begin(), p.end(), 0);
}
bool unite(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) return false;
p[pa] = pb;
--n;
return true;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};
class Solution {
public:
int maximumSafenessFactor(vector<vector<int>>& grid) {
int n = grid.size();
if (grid[0][0] || grid[n - 1][n - 1]) {
return 0;
}
queue<pair<int, int>> q;
int dist[n][n];
memset(dist, 0x3f, sizeof(dist));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j]) {
dist[i][j] = 0;
q.emplace(i, j);
}
}
}
int dirs[5] = {-1, 0, 1, 0, -1};
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] == 0x3f3f3f3f) {
dist[x][y] = dist[i][j] + 1;
q.emplace(x, y);
}
}
}
vector<tuple<int, int, int>> t;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
t.emplace_back(dist[i][j], i, j);
}
}
sort(t.begin(), t.end());
reverse(t.begin(), t.end());
UnionFind uf(n * n);
for (auto [d, i, j] : t) {
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= d) {
uf.unite(i * n + j, x * n + y);
}
}
if (uf.find(0) == uf.find(n * n - 1)) {
return d;
}
}
return 0;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88 | type unionFind struct {
p []int
n int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
for i := range p {
p[i] = i
}
return &unionFind{p, n}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
if uf.find(a) == uf.find(b) {
return false
}
uf.p[uf.find(a)] = uf.find(b)
uf.n--
return true
}
func maximumSafenessFactor(grid [][]int) int {
n := len(grid)
if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
return 0
}
q := [][2]int{}
dist := make([][]int, n)
const inf = 1 << 30
for i := range dist {
dist[i] = make([]int, n)
for j := range dist[i] {
dist[i][j] = inf
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
dist[i][j] = 0
q = append(q, [2]int{i, j})
}
}
}
dirs := [5]int{-1, 0, 1, 0, -1}
for len(q) > 0 {
p := q[0]
q = q[1:]
i, j := p[0], p[1]
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && dist[x][y] == inf {
dist[x][y] = dist[i][j] + 1
q = append(q, [2]int{x, y})
}
}
}
t := [][3]int{}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
t = append(t, [3]int{dist[i][j], i, j})
}
}
sort.Slice(t, func(i, j int) bool {
return t[i][0] > t[j][0]
})
uf := newUnionFind(n * n)
for _, p := range t {
d, i, j := p[0], p[1], p[2]
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= d {
uf.union(i*n+j, x*n+y)
}
}
if uf.find(0) == uf.find(n*n-1) {
return d
}
}
return 0
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80 | class UnionFind {
private p: number[];
private n: number;
constructor(n: number) {
this.n = n;
this.p = Array(n)
.fill(0)
.map((_, i) => i);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
const pa = this.find(a);
const pb = this.find(b);
if (pa !== pb) {
this.p[pa] = pb;
this.n--;
return true;
}
return false;
}
}
function maximumSafenessFactor(grid: number[][]): number {
const n = grid.length;
if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
return 0;
}
const q: number[][] = [];
const inf = 1 << 30;
const dist: number[][] = Array(n)
.fill(0)
.map(() => Array(n).fill(inf));
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
dist[i][j] = 0;
q.push([i, j]);
}
}
}
const dirs = [-1, 0, 1, 0, -1];
while (q.length) {
const [i, j] = q.shift()!;
for (let k = 0; k < 4; ++k) {
const [x, y] = [i + dirs[k], j + dirs[k + 1]];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] === inf) {
dist[x][y] = dist[i][j] + 1;
q.push([x, y]);
}
}
}
const t: number[][] = [];
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
t.push([dist[i][j], i, j]);
}
}
t.sort((a, b) => b[0] - a[0]);
const uf = new UnionFind(n * n);
for (const [d, i, j] of t) {
for (let k = 0; k < 4; ++k) {
const [x, y] = [i + dirs[k], j + dirs[k + 1]];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x][y] >= d) {
uf.union(i * n + j, x * n + y);
}
}
if (uf.find(0) == uf.find(n * n - 1)) {
return d;
}
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102 | use std::collections::VecDeque;
impl Solution {
pub fn maximum_safeness_factor(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
if grid[0][0] == 1 || grid[n - 1][n - 1] == 1 {
return 0;
}
let inf: i32 = 1 << 30;
let mut dist = vec![vec![inf; n]; n];
let mut q = VecDeque::new();
for i in 0..n {
for j in 0..n {
if grid[i][j] == 1 {
dist[i][j] = 0;
q.push_back((i as i32, j as i32));
}
}
}
let dirs = [-1, 0, 1, 0, -1];
while let Some((i, j)) = q.pop_front() {
for k in 0..4 {
let x = i + dirs[k];
let y = j + dirs[k + 1];
if x >= 0 && x < n as i32 && y >= 0 && y < n as i32 {
let (x, y) = (x as usize, y as usize);
let (i, j) = (i as usize, j as usize);
if dist[x][y] == inf {
dist[x][y] = dist[i][j] + 1;
q.push_back((x as i32, y as i32));
}
}
}
}
let mut t: Vec<(i32, usize, usize)> = Vec::new();
for i in 0..n {
for j in 0..n {
t.push((dist[i][j], i, j));
}
}
t.sort_by(|a, b| b.0.cmp(&a.0));
let mut uf = UnionFind::new(n * n);
let dirs = [-1, 0, 1, 0, -1];
for (d, i, j) in t {
for k in 0..4 {
let x = i as i32 + dirs[k];
let y = j as i32 + dirs[k + 1];
if x >= 0 && x < n as i32 && y >= 0 && y < n as i32 {
let (x, y) = (x as usize, y as usize);
if dist[x][y] >= d {
uf.union(i * n + j, x * n + y);
}
}
}
if uf.find(0) == uf.find(n * n - 1) {
return d;
}
}
0
}
}
struct UnionFind {
p: Vec<usize>,
}
impl UnionFind {
fn new(n: usize) -> Self {
let mut p = vec![0; n];
for i in 0..n {
p[i] = i;
}
Self { p }
}
fn find(&mut self, x: usize) -> usize {
if self.p[x] != x {
self.p[x] = self.find(self.p[x]);
}
self.p[x]
}
fn union(&mut self, a: usize, b: usize) -> bool {
let pa = self.find(a);
let pb = self.find(b);
if pa == pb {
return false;
}
self.p[pa] = pb;
true
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100 | public class Solution {
public int MaximumSafenessFactor(IList<IList<int>> grid) {
int n = grid.Count;
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
return 0;
}
int inf = 1 << 30;
int[,] dist = new int[n, n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i, j] = inf;
}
}
Queue<(int x, int y)> q = new Queue<(int x, int y)>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
dist[i, j] = 0;
q.Enqueue((i, j));
}
}
}
int[] dirs = new int[] { -1, 0, 1, 0, -1 };
while (q.Count > 0) {
var (i, j) = q.Dequeue();
for (int k = 0; k < 4; k++) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x, y] == inf) {
dist[x, y] = dist[i, j] + 1;
q.Enqueue((x, y));
}
}
}
List<(int d, int i, int j)> t = new List<(int d, int i, int j)>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
t.Add((dist[i, j], i, j));
}
}
t.Sort((a, b) => b.d.CompareTo(a.d));
UnionFind uf = new UnionFind(n * n);
foreach (var (d, i, j) in t) {
for (int k = 0; k < 4; k++) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && dist[x, y] >= d) {
uf.Union(i * n + j, x * n + y);
}
}
if (uf.Find(0) == uf.Find(n * n - 1)) {
return d;
}
}
return 0;
}
}
public class UnionFind {
public int[] p;
public UnionFind(int n) {
p = new int[n];
for (int i = 0; i < n; i++) {
p[i] = i;
}
}
public int Find(int x) {
if (p[x] != x) {
p[x] = Find(p[x]);
}
return p[x];
}
public bool Union(int a, int b) {
int pa = Find(a);
int pb = Find(b);
if (pa == pb) {
return false;
}
p[pa] = pb;
return true;
}
}
|