Re: [閒聊] 每日leetcode
想不到
直接看hint 很簡潔明瞭
最多兩個0就可以切出一個獨立的island
我怎麼沒想到
我是智障
class Solution {
public:
int m;
int n;
void dfs(vector<vector<int>>& grid, int i, int j) {
if (grid[i][j] == -1 || grid[i][j] == 0) {
return;
}
grid[i][j] = -1;
int delta[5] = {0, 1, 0, -1, 0};
for (int k=0; k<4; k++) {
int next_i = i+delta[k];
int next_j = j+delta[k+1];
if (0<=next_i && next_i<this->m && 0<=next_j && next_j<this->n) {
dfs(grid, next_i, next_j);
}
}
return;
}
int numofIsland(vector<vector<int>>& grid) {
int num = 0;
for (int i=0; i<this->m; i++) {
for (int j=0; j<this->n; j++) {
if (grid[i][j] == 1) {
dfs(grid, i, j);
num += 1;
}
}
}
// reset grid
for (int i=0; i<this->m; i++) {
for (int j=0; j<this->n; j++) {
if (grid[i][j] == -1) {
grid[i][j] = 1;
}
}
}
return num;
}
int minDays(vector<vector<int>>& grid) {
this->m = grid.size();
this->n = grid[0].size();
if (numofIsland(grid) != 1) {
return 0;
}
for(int i=0; i<this->m; i++) {
for(int j=0; j<this->n; j++) {
if(grid[i][j] == 1) {
grid[i][j] = 0;
if (numofIsland(grid) != 1) {
return 1;
}
grid[i][j] = 1;
}
}
}
return 2;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723385921.A.61F.html
推
08/11 22:20,
1年前
, 1F
08/11 22:20, 1F
推
08/11 22:21,
1年前
, 2F
08/11 22:21, 2F
推
08/11 22:21,
1年前
, 3F
08/11 22:21, 3F
推
08/11 23:06,
1年前
, 4F
08/11 23:06, 4F
推
08/11 23:13,
1年前
, 5F
08/11 23:13, 5F
推
08/12 01:01,
1年前
, 6F
08/12 01:01, 6F
討論串 (同標題文章)
完整討論串 (本文為第 695 之 1548 篇)：