Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/10 16:41)推噓2(2推 0噓 1→)留言3則, 3人參與討論串692/1548 (看更多)
959. Regions Cut By Slashes
題目:
給你一個由字串組成的vector，假設長度為n，其中grid[i]代表對一個由n*n個1*1的
square的i-th row的切割法，每個小square可能切割法有"/" ，"\"，" "(不切割)三種
求出這個大square經過這些小square的切割後的region數
思路:
概念就是把"/" "\"這兩種分割代表成相鄰兩點沒有連結，然後求出compoment數，所以
用BFS DFS或是union find都可以解決問題，使用union find的話，概念上就是把任一個
小的1*1 square切成兩份當讀到兩種分割法時根據當前所在位置這兩個部分可以分別對上
或是左做union，如果是無分割，則將兩個部分union後一樣根據位置可以分別對上或左做
union，但須注意的是因為這樣我們每次都是把已造訪過的node union到新造訪node下，
所以並沒有真的用到path comprassion，所以最後判斷size時要對每一個點做一次find
才能得到正解，所以感覺如果是改成每次對未造訪的下和右邊的node做union並加上
union by rank結果才是最佳的?
int fin_d(int cur,vector<int> &ro_list){
if(ro_list[cur]!=cur){
ro_list[cur]=fin_d(ro_list[cur],ro_list);
}
return ro_list[cur];
}
void un_ion(int cur,int tar,vector<int> &ro_list){
ro_list[fin_d(cur,ro_list)]=fin_d(tar,ro_list);
}
int regionsBySlashes(vector<string>& grid) {
int n=grid.size();
vector<int> parent(2*n*n+1,-1);
for(int i=1;i<parent.size();++i){
parent[i]=i;
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(grid[i][j]==' '){
un_ion((i*(2*n)+2*j+1),(i*(2*n)+2*j+2),parent);
if(i>0){
if(grid[i-1][j]=='/'){
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+2),parent);
}
else{
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+1),parent);
}
}
if(j>0){
un_ion((i*(2*n)+2*j),(i*(2*n)+2*j+1),parent);
}
}
else if(grid[i][j]=='/'){
if(i>0){
if(grid[i-1][j]=='/'){
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+2),parent);
}
else{
un_ion((i*(2*n)+2*j+1),((i-1)*(2*n)+2*j+1),parent);
}
}
if(j>0){
un_ion((i*(2*n)+2*j+1),((i)*(2*n)+2*j),parent);
}
}
else{
//means grid[i][j]=='\'
if(i>0){
if(grid[i-1][j]=='/'){
un_ion((i*(2*n)+2*j+2),((i-1)*(2*n)+2*j+2),parent);
}
else{
un_ion((i*(2*n)+2*j+2),((i-1)*(2*n)+2*j+1),parent);
}
}
if(j>0){
un_ion((i*(2*n)+2*j+1),((i)*(2*n)+2*j),parent);
}
}
}
}
unordered_set<int> ans;
for(int i=1;i<parent.size();++i){
ans.insert(fin_d(parent[i],parent));
}
return ans.size();
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.239.43 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723279310.A.E00.html
→
08/10 16:50,
1年前
, 1F
08/10 16:50, 1F
推
08/10 16:51,
1年前
, 2F
08/10 16:51, 2F
推
08/10 17:48,
1年前
, 3F
08/10 17:48, 3F
討論串 (同標題文章)
完整討論串 (本文為第 692 之 1548 篇)：