Medium

题目描述

一个 n x n 的网格由 1 x 1 的正方形组成，其中每个 1 x 1 的正方形包含 '/'、'\' 或空格 ' '。这些字符将正方形分成连通区域。

给定表示网格的字符串数组 grid，返回区域的数量。

注意反斜杠字符是转义的，所以 '\' 表示为 '\\'。

示例 1：

输入：grid = [" /","/ "]
输出：2

示例 2：

输入：grid = [" /","  "]
输出：1

示例 3：

输入：grid = ["/\\","\\/"]
输出：5
解释：回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，"/\\" 表示 /\。

提示：

  • n == grid.length == grid[i].length
  • 1 <= n <= 30
  • grid[i][j] 是 '/'、'\' 或 ' '

解题思路

这道题的关键思路是将每个方格进一步细分，然后使用图遍历算法统计连通区域数量。

主要思路：

  1. 格子细分：将每个 1x1 的方格分成 3x3 的小格子。这样可以更精确地表示斜杠对区域的分割：

    • 空格 ' '：整个 3x3 区域都是连通的（全为1）
    • 正斜杠 '/'：从右上角到左下角的对角线为0，其余为1
    • 反斜杠 '\'：从左上角到右下角的对角线为0，其余为1

  2. 构建扩展网格：原来的 n x n 网格扩展为 3n x 3n 的二维数组，其中1表示可通行区域，0表示被斜杠阻挡的区域。

  3. 连通区域统计：对扩展后的网格进行DFS/BFS遍历，统计有多少个连通的区域。每次从一个未访问的1开始遍历，就找到了一个新的区域。

这种方法的优势是将复杂的斜杠分割问题转化为标准的二维网格连通性问题，思路清晰且易于实现。

推荐解法：使用DFS遍历扩展网格，时间复杂度合理，代码简洁。

代码实现

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        vector<vector<int>> expanded(3 * n, vector<int>(3 * n, 1));
        
        // 构建扩展网格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '/') {
                    expanded[3*i][3*j+2] = 0;
                    expanded[3*i+1][3*j+1] = 0;
                    expanded[3*i+2][3*j] = 0;
                } else if (grid[i][j] == '\\') {
                    expanded[3*i][3*j] = 0;
                    expanded[3*i+1][3*j+1] = 0;
                    expanded[3*i+2][3*j+2] = 0;
                }
            }
        }
        
        int regions = 0;
        function<void(int, int)> dfs = [&](int x, int y) {
            if (x < 0 || x >= 3*n || y < 0 || y >= 3*n || expanded[x][y] == 0) {
                return;
            }
            expanded[x][y] = 0;
            dfs(x+1, y);
            dfs(x-1, y);
            dfs(x, y+1);
            dfs(x, y-1);
        };
        
        for (int i = 0; i < 3*n; i++) {
            for (int j = 0; j < 3*n; j++) {
                if (expanded[i][j] == 1) {
                    dfs(i, j);
                    regions++;
                }
            }
        }
        
        return regions;
    }
};

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n = len(grid)
        expanded = [[1] * (3 * n) for _ in range(3 * n)]
        
        # 构建扩展网格
        for i in range(n):
            for j in range(n):
                if grid[i][j] == '/':
                    expanded[3*i][3*j+2] = 0
                    expanded[3*i+1][3*j+1] = 0
                    expanded[3*i+2][3*j] = 0
                elif grid[i][j] == '\\':
                    expanded[3*i][3*j] = 0
                    expanded[3*i+1][3*j+1] = 0
                    expanded[3*i+2][3*j+2] = 0
        
        def dfs(x, y):
            if x < 0 or x >= 3*n or y < 0 or y >= 3*n or expanded[x][y] == 0:
                return
            expanded[x][y] = 0
            dfs(x+1, y)
            dfs(x-1, y)
            dfs(x, y+1)
            dfs(x, y-1)
        
        regions = 0
        for i in range(3 * n):
            for j in range(3 * n):
                if expanded[i][j] == 1:
                    dfs(i, j)
                    regions += 1
        
        return regions

public class Solution {
    public int RegionsBySlashes(string[] grid) {
        int n = grid.Length;
        int[,] expanded = new int[3 * n, 3 * n];
        
        // 初始化为1
        for (int i = 0; i < 3 * n; i++) {
            for (int j = 0; j < 3 * n; j++) {
                expanded[i, j] = 1;
            }
        }
        
        // 构建扩展网格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '/') {
                    expanded[3*i, 3*j+2] = 0;
                    expanded[3*i+1, 3*j+1] = 0;
                    expanded[3*i+2, 3*j] = 0;
                } else if (grid[i][j] == '\\') {
                    expanded[3*i, 3*j] = 0;
                    expanded[3*i+1, 3*j+1] = 0;
                    expanded[3*i+2, 3*j+2] = 0;
                }
            }
        }
        
        int regions = 0;
        
        void Dfs(int x, int y) {
            if (x < 0 || x >= 3*n || y < 0 || y >= 3*n || expanded[x, y] == 0) {
                return;
            }
            expanded[x, y] = 0;
            Dfs(x+1, y);
            Dfs(x-1, y);
            Dfs(x, y+1);
            Dfs(x, y-1);
        }
        
        for (int i = 0; i < 3*n; i++) {
            for (int j = 0; j < 3*n; j++) {
                if (expanded[i, j] == 1) {
                    Dfs(i, j);
                    regions++;
                }
            }
        }
        
        return regions;
    }
}

var regionsBySlashes = function(grid) {
    const n = grid.length;
    const size = 3 * n;
    const matrix = Array(size).fill().map(() => Array(size).fill(0));
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const baseRow = i * 3;
            const baseCol = j * 3;
            
            if (grid[i][j] === '/') {
                matrix[baseRow][baseCol + 2] = 1;
                matrix[baseRow + 1][baseCol + 1] = 1;
                matrix[baseRow + 2][baseCol] = 1;
            } else if (grid[i][j] === '\\') {
                matrix[baseRow][baseCol] = 1;
                matrix[baseRow + 1][baseCol + 1] = 1;
                matrix[baseRow + 2][baseCol + 2] = 1;
            }
        }
    }
    
    let regions = 0;
    
    function dfs(row, col) {
        if (row < 0 || row >= size || col < 0 || col >= size || matrix[row][col] === 1) {
            return;
        }
        
        matrix[row][col] = 1;
        dfs(row - 1, col);
        dfs(row + 1, col);
        dfs(row, col - 1);
        dfs(row, col + 1);
    }
    
    for (let i = 0; i < size; i++) {
        for (let j = 0; j < size; j++) {
            if (matrix[i][j] === 0) {
                dfs(i, j);
                regions++;
            }
        }
    }
    
    return regions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)需要遍历扩展后的3n×3n网格，对每个位置最多访问一次
空间复杂度O(n²)需要额外的3n×3n数组存储扩展网格，递归调用栈深度最大为O(n²)