Re: [閒聊] 每日leetcode
※ 引述 《JIWP (神楽めあ的錢包)》 之銘言：
:
: 959. Regions Cut By Slashes
:
: 給n*n的grid
:
: 每一格可能包含3種元素'\'、'/'、' '
:
: 請問這個grid裡會有幾個area
:
思路:
沒有
我去看答案
練習union find
看到一個很酷的解法
就是把n*n個格子變成(n+1)*(n+1)個點
最開始每個在外圍的點是連在一起的union
然後對每個格子做一些小雞巴事
什麼情況會增加區域？
同一個union的點連在一起的時候
什麼時後union合併？
不同union連在一起的時候
做完之後就好了
第一次寫unionfind 好醜
```cpp
class Solution {
public:
vector<vector<int>> paper;
int n ;
int regionsBySlashes(vector<string>& grid)
{
n = grid.size();
int count = 1;
paper.resize(n+1,(vector<int>(n+1,0)));
int p = 0;
for(int i = 1 ; i < n ; i ++)
{
for(int j = 1 ; j < n ; j ++)
{
p = i*(n+1)+j;
paper[i][j] =p;
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
if(grid[i][j] == ' ')continue;
int a ;
int b ;
int c ;
int d ;
if(grid[i][j] == '/')
{
a = i;
b = j+1;
c = i+1;
d = j;
}
else if(grid[i][j] == '\\')
{
a = i;
b = j;
c = i+1;
d = j+1;
}
if(findoin(a,b) == findoin(c,d))
{
count ++;
}
else
{
oin(a,b,c,d);
}
}
}
return count;
}
int findoin(int i , int j)
{
int orig = i*(n+1) + j;
if(paper[i][j] != orig)
{
paper[i][j] = findoin( paper[i][j]/(n+1) , paper[i][j]%(n+1) );
}
return paper[i][j];
}
void oin(int a , int b , int c , int d )
{
int ai = paper[a][b]/(n+1);
int bi = paper[a][b]%(n+1);
int ci = paper[c][d]/(n+1);
int di = paper[c][d]%(n+1);
if(ai*(n+1)+bi < ci*(n+1)+di)paper[ci][di] = ai*(n+1)+bi;
else paper[ai][bi] = ci*(n+1)+di;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.39.139 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723278968.A.818.html
→
08/10 16:39,
1年前
, 1F
08/10 16:39, 1F
推
08/10 16:44,
1年前
, 2F
08/10 16:44, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 691 之 1548 篇)：