leetcode怎么实现由斜杠划分区域

本篇内容主要讲解“leetcode怎么实现由斜杠划分区域”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“leetcode怎么实现由斜杠划分区域”吧!

创新互联专注于企业网络营销推广、网站重做改版、芗城网站定制设计、自适应品牌网站建设、H5网站设计、星空体育app最新版本(2024已更新)制作、集团公司官网建设、成都外贸网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为芗城等各大城市提供网站开发制作服务。

一、题目内容

在由 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怎么实现由斜杠划分区域”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！

分享名称：leetcode怎么实现由斜杠划分区域
浏览地址：/article4/iisjoe.html

成都网站建设公司_创新互联，为您提供小程序开发、网站改版、服务器托管、、面包屑导航、微信小程序

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联