Number of Islands
2020/4/17
問題概要
https://gyazo.com/9d96710ba3d8714a3fc600f3c46545aa
$ n \times mの二次元配列上に0, 1がそれぞれプロットされてる
1の上下方向に隣り合った集まりを”島”としてカウントし、いくつ島が存在するか答えよ、という問題
解法
DFSでもBFSでも解けるので、両方で解いてみる
UnionFindでも解けるようなので、別解ページを書きたい
DFS
1に出会った時点で上下左右に隣接するマスを0に変えながら、マス全てを巡回すればok
最初に1に出会うタイミングでans++すれば良い
code:dfs.cpp
class Solution {
public:
int m, n;
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
if (m < 1) return 0;
int ans = 0;
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
traverse(grid, i, j);
ans++;
}
}
}
return ans;
}
void traverse(vector<vector<char>>& grid, int y, int x) {
for (auto dir : dirs) {
int ny = y+dir0, nx = x+dir1; if (ny < 0 || m <= ny || nx < 0 || n <= nx) continue;
if (gridnynx == '1') traverse(grid, ny, nx); }
}
};
BFS
上記のDFSの探索部分をBFSにしたもの
queue.pushするタイミングでそのマス目を0にしておくことで、後段のifで1になる判定がダブってしまうことを防ぐ
これを防がないと、重複するx, yペアがqueueに溜まってしまう 結果、計算量が増えて容易にTLEになる(遭遇した) code:bfs.cpp
class Solution {
public:
int max_y;
int max_x;
int cnt = 0;
int numIslands(vector<vector<char>>& grid) {
max_y = grid.size();
if (max_y < 1) return 0;
int ans = 0;
for (int i=0; i<max_y; i++) {
for (int j=0; j<max_x; j++) {
cout << ++cnt << endl;
ans++;
bfs(grid, i, j);
}
}
}
return ans;
}
void bfs(vector<vector<char>>& grid, int y, int x) {
queue<vector<int>> q;
q.push({y, x});
while (!q.empty()) {
vector<int> cur = q.front();
int ny = cur0, nx = cur1; cout << ny << " " << nx << endl;
q.pop();
if (0 <= ny-1 && gridny-1nx == '1') { q.push({ny-1, nx});
}
if (ny+1 < max_y && gridny+1nx == '1') { q.push({ny+1, nx});
}
if (0 <= nx-1 && gridnynx-1 == '1') { q.push({ny, nx-1});
}
if (nx+1 < max_x && gridnynx+1 == '1') { q.push({ny, nx+1});
}
}
}
};