959. Regions Cut By Slashes


题目

An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/''\', or blank space ' '. These characters divide the square into contiguous regions.

Given the grid grid represented as a string array, return the number of regions.

Note that backslash characters are escaped, so a '\' is represented as '\\'.

Example 1:

Input: grid = [" /","/ "]
Output: 2

Example 2:

Input: grid = [" /","  "]
Output: 1

Example 3:

Input: grid = ["/\\","\\/"]
Output: 5
Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.

Constraints:

  • n == grid.length == grid[i].length
  • 1 <= n <= 30
  • grid[i][j] is either '/''\', or ' '.

思路

leetcode959,非常有意思的一道题。

题目大意是,求用”/”和”\”分隔的N*N正方形中的连通区域个数。

思路是把每个1*1方格拆分成3*3方格,再常规dfs即可。

一图胜千言。

代码

class Solution(object):
    def regionsBySlashes(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        N = len(grid)
        N3 = N * 3
        traveled = [[False] * N3 for _ in range(N3)]
        grid3 = [[0] * N3 for _ in range(N3)]
        
        for i in range(N):
            for j in range(N):
                if grid[i][j] == '/':
                    grid3[i * 3][j * 3 + 2] = 1
                    grid3[i * 3 + 1][j * 3 + 1] = 1
                    grid3[i * 3 + 2][j * 3] = 1
                elif grid[i][j] == "\\":
                    grid3[i * 3][j * 3] = 1
                    grid3[i * 3 + 1][j * 3 + 1] = 1
                    grid3[i * 3 + 2][j * 3 + 2] = 1
        ret = 0
        def dfs(i, j):
            if i < 0 or i >= N3 or j < 0 or j >= N3:
                return
            if traveled[i][j] or grid3[i][j] == 1:
                return
            traveled[i][j] = True
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)
            
        for i in range(N3):
            for j in range(N3):
                if grid3[i][j] == 0 and not traveled[i][j]:
                    ret += 1
                    dfs(i, j)
        return ret

AC,收工!



——此处是内容的分割线——

除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.utopiafar.com/2022/11/25/leetcode-959-regions-cut-by-slashes/

码字不易,如果觉得内容有帮助,欢迎留言or点赞!


发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注