Re: [閒聊] 每日leetcode
思路:
先dfs找島嶼面積
然後對每個0找找看四周的島嶼面積
用Union find來確認是不是不同的島嶼
才不會重複算到
過年也要刷題
幹
||```cpp
class UnionFind {
vector<int> par, cnt;
public:
UnionFind(int n): par(n, -1), cnt(n, 1) { }
int find(int a) {
if(par[a] == -1) return a;
return par[a] = find(par[a]);
}
bool un(int a, int b) {
int pa = find(a);
int pb = find(b);
if(pa == pb) return 0;
if(cnt[pa] < cnt[pb]) swap(pa, pb);
cnt[pa] += cnt[pb];
par[pb] = pa;
return 1;
}
};
class Solution {
public:
int block;
UnionFind *uf;
vector<vector<int>> grid;
int nowi;
int nowj;
int n ;
int m ;
vector<vector<int>> pass;
void find(int i ,int j )
{
if(i >= n or i < 0 or j >= m or j < 0)return;
if(pass[i][j] == 1)return;
if(grid[i][j] == 0)return;
uf->un(i*m + j , nowi*m + nowj);
block ++;
pass[i][j] = 1;
find(i+1,j);
find(i-1,j);
find(i,j+1);
find(i,j-1);
}
void draw(int i ,int j )
{
if(i >= n or i < 0 or j >= m or j < 0)return;
if(pass[i][j] != 1)return;
pass[i][j] = block;
draw(i+1,j);
draw(i-1,j);
draw(i,j+1);
draw(i,j-1);
}
int largestIsland(vector<vector<int>>& grid87)
{
int res = 0;
grid = grid87;
n = grid.size();
m = grid[0].size();
pass.resize(n,vector<int>(m));
uf = new UnionFind(n*m);
block = 0;
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < m ; j ++)
{
nowi = i;
nowj = j;
if(grid[i][j] == 1 && pass[i][j] == 0)
{
block = 0;
find(i,j);
draw(i,j);
res = max(res,block);
}
}
}
// for(int i = 0 ; i < n ; i ++)
// {
// for(int j = 0 ; j < m ; j ++)
// {
// cout << pass[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
vector<int> dx = {0,0,1,-1};
vector<int> dy = {1,-1,0,0};
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < m ; j ++)
{
if(grid[i][j] == 0 )
{
vector<int> save;
int now = 1;
for(int d = 0 ; d < 4 ; d ++)
{
int ni = i + dx[d];
int nj = j + dy[d];
int ok = 1;
if(ni >= n or ni < 0 or nj >= m or nj < 0)continue;
int blocki = uf->find(ni*m+nj);
// cout << blocki << " ? " << i << " " << j << endl;
// cout << pass[ni][nj] << endl;
for(int k: save)
{
if(k == blocki)ok = 0;
}
save.push_back(blocki);
if(ok)now += pass[ni][nj];
}
res = max(res,now);
}
}
}
return res;
}
};
```||
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.169.39 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1738338916.A.F39.html
推
01/31 23:56,
10月前
, 1F
01/31 23:56, 1F
推
01/31 23:57,
10月前
, 2F
01/31 23:57, 2F
推
01/31 23:59,
10月前
, 3F
01/31 23:59, 3F
討論串 (同標題文章)
完整討論串 (本文為第 1318 之 1553 篇)：