leetcode怎么實現由斜杠劃分區域

本篇內容主要講解“leetcode怎么實現由斜杠劃分區域”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“leetcode怎么實現由斜杠劃分區域”吧!

一、題目內容

在由 1 x 1 方格組成的 N x N 網格 grid 中，每個 1 x 1 方塊由 /、\ 或空格構成。這些字符會將方塊劃分為一些共邊的區域。

（請注意，反斜杠字符是轉義的，因此 \ 用 "\\" 表示。）。

返回區域的數目。

示例 1：

輸入：
[
  " /",
  "/ "
]
輸出：2
解釋：2x2 網格如下：

示例 2：

輸入：
[
  " /",
  "  "
]
輸出：1
解釋：2x2 網格如下：

示例 3：

輸入：
[
  "\\/",
  "/\\"
]
輸出：4
解釋：（回想一下，因為 \ 字符是轉義的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 網格如下：

示例 4：

輸入：
[
  "/\\",
  "\\/"
]
輸出：5
解釋：（回想一下，因為 \ 字符是轉義的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 網格如下：

示例 5：

輸入：
[
  "//",
  "/ "
]
輸出：3
解釋：2x2 網格如下：

提示：

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

二、解題思路

三角形由三個邊構成，那么三個點兩兩都連通則區域加1。

首先先將大格子的邊上的點進行連通，然后再處理斜線‘/’上的點，連通則區域加1，不連通則將兩個點進行連通，接著同樣處理‘\'，說白了就是三角形的頂點到達另一個頂點既可以直接通過相連的線段到達，也可以經過除二者之外的另一個頂點再到達。

總之連通就是這個意思~

三、代碼

from collections import defaultdict
class Solution:
    def regionsBySlashes(self, grid: list) -> int:
        root = defaultdict(tuple)

        def find(x):
            if x != root[x]:
                root[x] = find(root[x])
                # return root[x]
            return root[x]

        # 檢測x和y是否連通
        def connected(x, y):
            return find(x) == find(y)

        # 連通x和y
        def union(x, y):
            if connected(x, y) is False:
                root[find(x)] = find(y)

        # 存儲大格子所有點坐標
        for i in range(len(grid) + 1):
            for j in range(len(grid) + 1):
                root[(i, j)] = (i, j)

        # 左斜上三角的點進行連通
        for i in range(len(grid) + 1):
            union((0, 0), (0, i))
            union((0, 0), (i, 0))

        # 右斜下三角的點進行連通
        for i in range(len(grid) + 1):
            union((i, len(grid)), (len(grid), len(grid)))
            union((len(grid), i), (len(grid), len(grid)))

        # 這樣大格子邊上的點都進行了連通

        res = 1  # 連通區域個數

        for i in range(len(grid)):
            for j in range(len(grid)):
                if grid[i][j] == '/':
                    # 小格子的左下角和右上角之前已經連通了
                    if connected((i + 1, j), (i, j + 1)):
                        res += 1  # 個數加1
                    else:
                        # 否則小格子的左下角和右上角進行連通
                        union((i + 1, j), (i, j + 1))

                elif grid[i][j] == '\\':
                    # 小格子的左上角和右下角之前已經連通了
                    if connected((i, j), (i + 1, j + 1)):
                        res += 1  # 個數加1
                    else:
                        # 否則小格子的左上角和右下角進行連通
                        union((i, j), (i + 1, j + 1))

        return res


if __name__ == '__main__':
    grid = [
              "/\\",
              "\\/"
            ]
    s = Solution()
    ans = s.regionsBySlashes(grid)
    print(ans)

到此，相信大家對“leetcode怎么實現由斜杠劃分區域”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！