由斜杠划分区域 图解题解

斜线把网格切成几块，到底在数什么

给一个 n×n 的网格 grid，每格是斜杠 /、反斜杠 \ 或空格。斜线把所在方块从中间切开，相邻方块之间没有线挡着的部分连成一片，问整张图被切出多少块互不相连的区域。题面第三个例子 grid = ["/\\","\\/"] 是 2×2 网格，四条斜线交错切成 5 块，答案 5。反斜杠在字符串里写成两个 \\，读出来仍是一个字符。

为什么不能顺着线直接圈出一块块区域

斜线画在方块内部，一条 / 把格子劈成左上、右下两半，这两半各自还可能跟上下左右的邻居连通。一块区域常横跨好几个格子、形状犬牙交错，想沿着线一圈圈描出来难框准。难在『连通』是跨格子的、『切开』却发生在格子里，两件事缠在一起。

把一个格子拆成四个三角这一步

把每个格子沿两条对角线剁成上、右、下、左四个三角。一条斜线就变成『格内某两对三角归一堆、另两对归另一堆』的规则。斜杠 / 连上三角和左三角、连右三角和下三角；反斜杠 \ 反过来连上右、连下左；空格没有线，四个三角全通成一块。

谁和谁连通用并查集记——它能把互相到达的三角随时归到同一组。起手 4n² 个三角各自成组，每合并一次组数减一。最后剩多少组，就是多少个连通分量，也就是图里互相连得到的一撮三角，对应多少块区域。

格子内部连完，还要缝上相邻格的边

光连格内不够，相邻两格挨着那条边上的两个贴脸三角本就是同一片。四个三角定死编号 0 上、1 右、2 下、3 左：当前格下边有格子，就把下三角 2 并到下邻格上三角 0；右边有格子，就把右三角 1 并到右邻格左三角 3。每格只往下、往右看，同一条公共边就不会被两边重复缝。

拿题面那张 2×2 图亲手并一遍

四个格子铺开：(0,0) 是 /、(0,1) 是 \、(1,0) 是 \、(1,1) 是 /，共 16 个三角、16 组。先看 (0,0)：下、右都有格子，跟下邻、右邻各并一次，16 压到 14；再按 / 把上左、右下各并一次，降到 12。

(0,1) 的 \：右边到头，跟下邻并一次，再按 \ 连上右、连下左，到 9。(1,0) 的 \：下边到头，跟右邻并一次，再内部连两次，到 6。(1,1) 的 /：本该连的一对一查已在同一组、空转，组数不动；再连另一对减到 5。走完剩 5 组，正是题面要的 5。

转义符看走眼，所有反斜杠分支就全废了

三角总数 4n²，每格只做常数次合并，并查集带路径压缩后每步近似 O(1)，总时间 O(n²·α)，α 是增长极慢、可当常数看的反阿克曼函数；再用数组存这 4n² 个三角的归属，空间 O(n²)。

这几处最容易写坏。反斜杠在字符串里是两个 \、读出来是单个 \，若拿它跟两个字符比，所有 \ 分支都不触发，反斜杠格全连错。格间那步最容易漏：只连格内、不缝相邻格的边，本该连成一片的会被拆成好几块，答案偏大。编号也得对死，跟斜线连法一错位，同块被劈开、异块被硬凑一起。

两个小边界顺带验：整张图就一个空格，四个三角全通、只算 1 块；一个格子里只有一条斜线，切成 2 块——贴外框的单条线封不出新区域，得靠格与格接力才切出更多块。

Python

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

C++

#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];
    }
};

Java

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;
    }
}