959. Regions Cut By Slashes(Leetcode每日一题-2021.01.25)--抄答案

本文主要是介绍959. Regions Cut By Slashes(Leetcode每日一题-2021.01.25)--抄答案，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, , or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as “\”.)

Return the number of regions.

Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either ‘/’, ‘’, or ’ ’

Example1

在这里插入图片描述

Example2

在这里插入图片描述

Example3

在这里插入图片描述

Example4

在这里插入图片描述

Example5

在这里插入图片描述

Solution

// 模板2，维护连通分量的并查集格式
class UnionFind{vector<int> parent;int count;
public:// 初始化UnionFind(int n):parent(vector<int>(n)),count(n){for(int i = 0;i < n;i++){parent[i] = i;}}int getcount(){return count;}// 查找操作int Find(int x){if(parent[x] != x)parent[x] = Find(parent[x]);return parent[x];}// 合并操作,才需要对连通分量进行递减，注意要先判断相同的就不用递减void Union(int x,int y){int rootx = Find(x);int rooty = Find(y);if(rootx == rooty){return;}parent[rootx] = rooty;count--;}
};
class Solution {
public://方法一：并查集思路，将小单元格划分为0、1、2、3区域,并查集遇到/合并03，12,遇到\合并01、23,空格合并全部// 单元格之间的合并是向右或向下扫描相邻的区域，需要维护并查集的连通分量个数4*N*Nint regionsBySlashes(vector<string>& grid) {int N = grid.size();int size = 4*N*N;UnionFind uf(size);for(int i = 0;i < N;i++){vector<char> row(grid[i].begin(),grid[i].end());for(int j = 0;j < N;j++){// 二维网格转化为一维表格公式int index = 4 * (i * N + j);char c = row[j];// 单元格内的合并if(c == '/'){// 合并0、3，合并1、2uf.Union(index,index+3);uf.Union(index+1,index+2);}else if(c == '\\'){// 合并0、1，合并2、3uf.Union(index,index+1);uf.Union(index+2,index+3);}else{uf.Union(index,index+1);uf.Union(index+1,index+2);uf.Union(index+2,index+3);}// 单元格间的合并// 向右边合并1(当前):3(右一列)if(j + 1 < N)uf.Union(index+1,4 * (i * N + j + 1) + 3);// 向下边合并2(当前):0(下一行)if(i + 1 < N)uf.Union(index+2,4 * ((i + 1) * N + j));}}return uf.getcount();}
};
//https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/you-xie-gang-hua-fen-qu-yu-by-leetcode-67xb/