🔗 🟡 2812. Find the Safest Path in a Grid 2154

題意

給定一個下標從 00 開始，大小為 n×nn \times n 的二維矩陣 gridgrid，其中 (r,c)(r, c) 代表：

  • 如果 grid[r][c]=1grid[r][c] = 1，則表示一個存在小偷的單元格
  • 如果 grid[r][c]=0grid[r][c] = 0，則表示該單元格為空

從單元格 (0,0)(0, 0) 開始。在每次移動中，可以移動到矩陣中四個方向上的任何相鄰單元格，包括存在小偷的單元格。

路徑的 安全係數(safeness factor) 被定義為路徑上所有單元格到最近的小偷的 曼哈頓距離(manhattan distance) 的最小值。

返回到達格子 (n−1,n−1)(n - 1, n - 1) 的所有路徑中的 最大安全係數(safeness factor) 。

首先用多源BFS計算每個點到最近的 11 的曼哈頓距離，如此便可以把問題轉換成：是否存在一條從起點到終點的路徑，使得每個點到最近的 11 的距離都 ≥x\geq x。

從 最大化最小值 的角度出發，可以想到對答案二分，對於每個可能的答案 xx ，檢查是否存在從起點 (0,0)(0, 0) 到終點 (n−1,n−1)(n-1, n-1) 的路徑，使得每個點到最近的 11 的距離都 ≥x\geq x。

而檢查是否存在這樣的路徑，可以用 DFS/BFS/DSU 來實現，下面範例使用 BFS 來實現。

由於題目確保至少存在一個小偷，而小偷到其他點的距離一定不超過 2n−22n-2 ，因此二分答案的範圍為 [0,2n−2][0, 2n-2] 。

複雜度分析

  • 時間複雜度：O(n2log⁡n)O(n^2 \log n)
  • 空間複雜度：O(n2)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
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 多源BFS計算每個點到最近的 1 的曼哈頓距離
        dist = [[-1] * n for _ in range(n)] 
        q = deque()
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    dist[i][j] = 0
                    q.append((i, j, 0))
        while q:
            i, j, d = q.popleft()
            for nx, ny in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == -1:
                    dist[nx][ny] = d + 1
                    q.append((nx, ny, d+1))
        # 對答案二分，這裡使用BFS來檢查是否存在一條路徑
        def check(x):
            if dist[0][0] < x:
                return False
            visited = [[False] * n for _ in range(n)]
            q = deque([(0, 0)])
            visited[0][0] = True
            while q:
                i, j = q.popleft()
                if i == n-1 and j == n-1:
                    return True
                for nx, ny in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                    if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and dist[nx][ny] >= x:
                        visited[nx][ny] = True
                        q.append((nx, ny))
            return False
        left, right = 0, 2*n-2 # [0, 2n-2]
        while left <= right: # 區間不為空
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return right
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
class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        int DIR[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        // 多源BFS計算每個點到最近的 1 的曼哈頓距離
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<tuple<int, int, int>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.push({i, j, 0});
                }
            }
        }
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            int i = get<0>(t), j = get<1>(t), d = get<2>(t);
            for (int k = 0; k < 4; k++) {
                int nx = i + DIR[k][0], ny = j + DIR[k][1];
                if (0 <= nx && nx < n && 0 <= ny && ny < n && dist[nx][ny] == -1) {
                    dist[nx][ny] = d + 1;
                    q.push({nx, ny, d+1});
                }
            }
        }
        // 對答案二分，這裡使用BFS來檢查是否存在一條路徑
        function<bool(int)> check = [&](int x) {
            if (dist[0][0] < x) return false;
            vector<vector<bool>> visited(n, vector<bool>(n, false));
            queue<pair<int, int>> q;
            q.push({0, 0});
            visited[0][0] = true;
            while (!q.empty()) {
                auto p = q.front(); q.pop();
                int i = p.first, j = p.second;
                if (i == n-1 && j == n-1) return true;
                for (int k = 0; k < 4; k++) {
                    int nx = i + DIR[k][0], ny = j + DIR[k][1];
                    if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny] && dist[nx][ny] >= x) {
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
            return false;
        };
        int left = 0, right = (n << 1) - 2; // [0, 2n-2]
        while (left <= right) { // 區間不為空
            int mid = (left + right) / 2;
            if (check(mid)) left = mid + 1;
            else right = mid - 1;
        }
        return right;
    }
};

方法二：多源BFS + DSU

同樣預處理每個點到最近的 1 的曼哈頓距離，但是在判斷連通性時，可以改用 DSU 來實現，並且不用每次都重新建圖，而是事先保存曼哈頓距離到點的對應關係，然後從最大距離開始枚舉 xx ，遍歷距離為 xx 的點，若周圍有距離 ≥x\geq x 的點，則合併這些點，最後判斷起點和終點是否在同一個集合中。

由於每個點只會遍歷一次，而 DSU 的時間複雜度可以視為 O(1)O(1) ，因此時間複雜度約為 O(n2)O(n^2) 。

複雜度分析

  • 時間複雜度：O(n2α(n2))O(n^2 \alpha(n^2))，其中 α(n)\alpha(n) 為Ackermann函數的反函數 ，是一個極為緩慢增長的函數。
  • 空間複雜度：O(n2)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
class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 多源BFS計算每個點到最近的 1 的曼哈頓距離
        dist = [[-1] * n for _ in range(n)] 
        q = deque()
        groups = defaultdict(list) # 保存距離到點的對應關係
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    dist[i][j] = 0
                    q.append((i, j, 0))
                    groups[0].append((i, j))
        while q:
            i, j, d = q.popleft()
            for nx, ny in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == -1:
                    dist[nx][ny] = d + 1
                    q.append((nx, ny, d+1))
                    groups[d+1].append((nx, ny))
        # DSU
        fa = [i for i in range(n*n)] # 將二維座標轉換為一維
        def find(x):
            if x != fa[x]:
                fa[x] = find(fa[x])
            return fa[x]
        def union(x, y):
            x, y = find(x), find(y)
            if x != y:
                fa[x] = y
        # 從最大距離開始枚舉 x
        for d in range(max(groups.keys()), 0, -1):
            for i, j in groups[d]:
                for nx, ny in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                    if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] >= d: # 周圍有距離 >= x 的點，則使其連通
                        union(i*n+j, nx*n+ny)
                if find(0) == 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
class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        int DIR[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        // 多源BFS計算每個點到最近的 1 的曼哈頓距離
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<tuple<int, int, int>> q;
        int mx = 0; // 最大距離
        unordered_map<int, vector<pair<int, int>>> groups; // 保存距離到點的對應關係
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.push({i, j, 0});
                    groups[0].push_back({i, j});
                }
            }
        }
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            int i = get<0>(t), j = get<1>(t), d = get<2>(t);
            for (int k = 0; k < 4; k++) {
                int nx = i + DIR[k][0], ny = j + DIR[k][1];
                if (0 <= nx && nx < n && 0 <= ny && ny < n && dist[nx][ny] == -1) {
                    dist[nx][ny] = d + 1;
                    q.push({nx, ny, d+1});
                    groups[d+1].push_back({nx, ny});
                    mx = max(mx, d+1);
                }
            }
        }
        // Disjoint Set Union (DSU)
        vector<int> fa(n*n);
        iota(fa.begin(), fa.end(), 0); // init
        function<int(int)> find = [&](int x) {
            return x == fa[x] ? x : fa[x] = find(fa[x]);
        };
        function<void(int, int)> union_ = [&](int x, int y) {
            x = find(x), y = find(y);
            if (x != y) fa[x] = y;
        };
        // 從最大距離開始枚舉 x
        for (int d = mx; d >= 0; d--) {
            for (auto p : groups[d]) {
                int i = p.first, j = p.second;
                for (int k = 0; k < 4; k++) {
                    int nx = i + DIR[k][0], ny = j + DIR[k][1];
                    if (0 <= nx && nx < n && 0 <= ny && ny < n && dist[nx][ny] >= d) { // 周圍有距離 >= x 的點，則使其連通
                        union_(i*n+j, nx*n+ny);
                    }
                }
                if (find(0) == find(n*n-1)) return d;
            }
        }
        return 0;
    }
};

參考資料

寫在最後

Cover photo is generated by @たろたろ, thanks for their work!

雖然還是一直保持做題的習慣，但很久沒有寫解題紀錄了，還是需要花費數倍於做題的時間在寫解題記錄上。
而強迫自己每天都寫解題紀錄還是會讓自己感到有點疲憊，導致咕咕🕊️了很多解題紀錄沒寫，未來應該會先改成想到才寫的形式。