由斜杠划分区域 图解题解

这道题到底在问什么

输入

grid = [" /","/ "]

输出

2

输入

grid = [" /"," "]

输出

1

输入

grid = ["/\\","\\/"]

输出

5 （本课就用这个 2×2 例子）

最优解：一步一步想明白

1. 3核心一句话:每格拆 4 三角,格内按斜杠连、格间按相邻连,最后数连通块。下面每帧都在套它。
2. 4左上 / · 右上 \ · 左下 \ · 右下 /先看清输入。四个格子各有一条斜线:左上和右下是斜杠 /,右上和左下是反斜杠 \。眼睛先想象一下这四条线把图切成了几块,等会用并查集把它精确数出来。
3. 5每格 4 三角,共 16 个第一步:把每个格子拆成 4 个三角,围成一个菱形,上是 0、右是 1、下是 2、左是 3,整张图一共 16 个三角。一开始谁也不连谁,连通块数就是 16。接下来一格一格地合并。
4. 6编号 0 1 2 3轮到第 (0,0) 个格子,它的四个三角编号是 0、1、2、3。这格写的是 斜杠 /,它把「上和左」连成一块、「右和下」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
5. 7连通块 16 → 15三角 2 是当前格的下三角,贴着下方格子的上三角 8,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 16 减到 15。
6. 8连通块 15 → 14三角 1 是当前格的右三角,贴着右边格子的左三角 7,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 15 减到 14。
7. 9连通块 14 → 13按这条斜线,格内三角 0 和 3 属于同一块,合并。两块并成一块,连通块数从 14 减到 13。
8. 10连通块 13 → 12按这条斜线,格内三角 1 和 2 属于同一块,合并。两块并成一块,连通块数从 13 减到 12。
9. 11编号 4 5 6 7轮到第 (0,1) 个格子,它的四个三角编号是 4、5、6、7。这格写的是 反斜杠 \,它把「上和右」连成一块、「下和左」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
10. 12连通块 12 → 11三角 6 是当前格的下三角,贴着下方格子的上三角 12,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 12 减到 11。
11. 13连通块 11 → 10按这条斜线,格内三角 4 和 5 属于同一块,合并。两块并成一块,连通块数从 11 减到 10。
12. 14连通块 10 → 9按这条斜线,格内三角 6 和 7 属于同一块,合并。两块并成一块,连通块数从 10 减到 9。
13. 15当前连通块 9上面一行两个格子处理完了,合并了几次之后,连通块数现在是 9。还剩下一行没处理,继续往下走。
14. 16编号 8 9 10 11轮到第 (1,0) 个格子,它的四个三角编号是 8、9、10、11。这格写的是 反斜杠 \,它把「上和右」连成一块、「下和左」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
15. 17连通块 9 → 8三角 9 是当前格的右三角,贴着右边格子的左三角 15,中间没有斜线,必然连通,合并。两块并成一块,连通块数从 9 减到 8。
16. 18连通块 8 → 7按这条斜线,格内三角 8 和 9 属于同一块,合并。两块并成一块,连通块数从 8 减到 7。
17. 19连通块 7 → 6按这条斜线,格内三角 10 和 11 属于同一块,合并。两块并成一块,连通块数从 7 减到 6。
18. 20编号 12 13 14 15轮到第 (1,1) 个格子,它的四个三角编号是 12、13、14、15。这格写的是 斜杠 /,它把「上和左」连成一块、「右和下」连成另一块。先看它和邻居的连接,再按这条斜线连内部。
19. 21连通块仍 6要连三角 12 和 15,可一查它们已经在同一个连通块里了,这一步什么都不做,连通块数保持 6。这正是并查集省事的地方:重复的连接自动被忽略,不会重复计数。
20. 22连通块 6 → 5按这条斜线,格内三角 13 和 14 属于同一块,合并。两块并成一块,连通块数从 6 减到 5。
21. 23区域数 = 5四个格子全部处理完。屏幕上同色的三角属于同一个区域,数一数一共有 5 种颜色,也就是 5 个连通块。这张图被斜线切成了 5 块,答案就是 5。
22. 24答案 = 5再回看一遍:每一种颜色就是一块独立区域。斜杠和反斜杠在中间交错,把网格切出了 5 块互不相连的区域。最终答案 5。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def union(a, b):
            pa, pb = find(a), find(b)
            if pa != pb:
                p[pa] = pb
                nonlocal size
                size -= 1

        n = len(grid)
        size = n * n * 4
        p = list(range(size))
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                k = i * n + j
                if i < n - 1:
                    union(4 * k + 2, (k + n) * 4)
                if j < n - 1:
                    union(4 * k + 1, (k + 1) * 4 + 3)
                if v == '/':
                    union(4 * k, 4 * k + 3)
                    union(4 * k + 1, 4 * k + 2)
                elif v == '\\':
                    union(4 * k, 4 * k + 1)
                    union(4 * k + 2, 4 * k + 3)
                else:
                    union(4 * k, 4 * k + 1)
                    union(4 * k + 1, 4 * k + 2)
                    union(4 * k + 2, 4 * k + 3)
        return size

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> p;
    int size;

    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        size = n * n * 4;
        p.resize(size);
        for (int i = 0; i < size; ++i) p[i] = i;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int k = i * n + j;
                if (i < n - 1) merge(4 * k + 2, (k + n) * 4);
                if (j < n - 1) merge(4 * k + 1, (k + 1) * 4 + 3);
                char v = grid[i][j];
                if (v == '/') {
                    merge(4 * k, 4 * k + 3);
                    merge(4 * k + 1, 4 * k + 2);
                } else if (v == '\\') {
                    merge(4 * k, 4 * k + 1);
                    merge(4 * k + 2, 4 * k + 3);
                } else {
                    merge(4 * k, 4 * k + 1);
                    merge(4 * k + 1, 4 * k + 2);
                    merge(4 * k + 2, 4 * k + 3);
                }
            }
        }
        return size;
    }

    void merge(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) return;
        p[pa] = pb;
        --size;
    }

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int[] p;
    private int size;

    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        size = n * n * 4;
        p = new int[size];
        for (int i = 0; i < p.length; ++i) {
            p[i] = i;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int k = i * n + j;
                if (i < n - 1) {
                    union(4 * k + 2, (k + n) * 4);
                }
                if (j < n - 1) {
                    union(4 * k + 1, (k + 1) * 4 + 3);
                }
                char v = grid[i].charAt(j);
                if (v == '/') {
                    union(4 * k, 4 * k + 3);
                    union(4 * k + 1, 4 * k + 2);
                } else if (v == '\\') {
                    union(4 * k, 4 * k + 1);
                    union(4 * k + 2, 4 * k + 3);
                } else {
                    union(4 * k, 4 * k + 1);
                    union(4 * k + 1, 4 * k + 2);
                    union(4 * k + 2, 4 * k + 3);
                }
            }
        }
        return size;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    private void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) {
            return;
        }
        p[pa] = pb;
        --size;
    }
}

复杂度

面试官可能追问