島の数

非常に古典的な検索問題。要素の各位置が訪問されたことを記録するために訪問した追加のブール配列で、現在の位置に関連付けられた各1の深さ優先探索から始まる配列をトラバース、訪問した各トラバース位置は真としてマークされます。

コードは以下の通り：

class Solution {
public:
 vector<vector<bool>> visited;
 int res = 0, rows, cols;
 int dx[4] = {1, 0, 0, -1}, dy[4] = {0, 1, -1, 0}; //これら2つの配列は、x, y, yの方向を表す。
 
 void DFS(int x, int y, vector<vector<bool>>& visited, vector<vector<char>>& grid) {
 visited[x][y] = true;
 for(int i = 0; i < 4; ++i) { //4方向の探索
 int newX = x + dx[i], newY = y + dy[i]; //次の位置を計算する
 if(newX < 0 || newX >= rows || newY < 0 || newY >= cols || grid[newX][newY] != '1' || visited[newX][newY]) { //新しい位置が範囲外であるか、1でないか、すでに訪問済みであれば、それをスキップする。
 continue;
 }
 DFS(newX, newY, visited, grid); //そうでなければ、検索は次の位置からリンクされた1まで続けられる。
 }
 }
 int numIslands(vector<vector<char>>& grid) { 
 if(grid.size() == 0 || grid[0].size() == 0) {
 return 0;
 }
 rows = grid.size(), cols = grid[0].size();
 visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
 for(int i = 0; i < rows; ++i) {
 for(int j = 0; j < cols; ++j) {
 if(grid[i][j] == '1' && !visited[i][j]) { //未訪問の土地の開始点を見つけ、アンサーカウントを更新し、この位置からDFSを開始し、彼にリンクしているすべての1を見つけ、visited配列を更新する。
 ++res;
 DFS(i, j, visited, grid);
 }
 }
 }
 return res;
 }
};