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

（請注意，反斜杠字符是轉(zhuǎn)義的，因此 \ 用 “\” 表示。）。

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

示例 1：

輸入：
[
" /",
"/ "
]
輸出：2

代碼

class Solution {int[] fa;public void init(){for(int i=0;i<fa.length;i++)fa[i]=i;}public int find(int x){if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];}public void union(int x,int y){x=find(x);y=find(y);if(x==y) return;fa[x]=y;}public int regionsBySlashes(String[] grid) {int n=grid.length;fa=new int[n*n*4];//將每個節(jié)點分成4份 // \ 0/3 | 1 // / 2\ init();for(int i=0;i<n;i++)for(int j=0;j<n;j++){int cur=i*n+j;//當(dāng)前節(jié)點if(i<n-1)//與左邊節(jié)點的3號相鄰{union(cur*4+2,(n*(i+1)+j)*4);}if(j<n-1)//與下邊節(jié)點的0號相鄰union(cur*4+1,(i*n+j+1)*4+3);if(grid[i].charAt(j)=='\\') \\分成 0 1 和 2 3{union(cur*4,cur*4+1);union(cur*4+2,cur*4+3);}else if(grid[i].charAt(j)=='/')\\分成 0 3 和 2 1{union(cur*4,cur*4+3);union(cur*4+2,cur*4+1);}else {//分成 0 1 2 3union(cur * 4, cur * 4 + 3);union(cur * 4 + 2, cur * 4 + 1);union(cur * 4 + 2, cur * 4 + 3);}}Set<Integer> set=new HashSet<>();//計算連通分量的個數(shù)for(int i=0;i<n*n*4;i++){set.add(find(i));}return set.size();} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的leetcode 959. 由斜杠划分区域（并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。