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

創(chuàng)新互聯(lián)專注于企業(yè)網(wǎng)絡營銷推廣、網(wǎng)站重做改版、薌城網(wǎng)站定制設計、自適應品牌網(wǎng)站建設、H5網(wǎng)站設計、商城網(wǎng)站制作、集團公司官網(wǎng)建設、成都外貿網(wǎng)站建設、高端網(wǎng)站制作、響應式網(wǎng)頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為薌城等各大城市提供網(wǎng)站開發(fā)制作服務。

一、題目內容

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

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

返回區(qū)域的數(shù)目。

示例 1：

輸入：
[
  " /",
  "/ "
]
輸出：2
解釋：2x2 網(wǎng)格如下：

示例 2：

輸入：
[
  " /",
  "  "
]
輸出：1
解釋：2x2 網(wǎng)格如下：

示例 3：

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

示例 4：

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

示例 5：

輸入：
[
  "//",
  "/ "
]
輸出：3
解釋：2x2 網(wǎng)格如下：

提示：

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

二、解題思路

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

首先先將大格子的邊上的點進行連通，然后再處理斜線‘/’上的點，連通則區(qū)域加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  # 連通區(qū)域個數(shù)

        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  # 個數(shù)加1
                    else:
                        # 否則小格子的左下角和右上角進行連通
                        union((i + 1, j), (i, j + 1))

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

        return res


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

到此，相信大家對“l(fā)eetcode怎么實現(xiàn)由斜杠劃分區(qū)域”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！

分享名稱：leetcode怎么實現(xiàn)由斜杠劃分區(qū)域
瀏覽地址：http://jinyejixie.com/article4/iisjoe.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、網(wǎng)站改版、服務器托管、、面包屑導航、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)