深さ優先探索

Leetcodeソリューションシリーズ-島の最大面積（c ++バージョン）



Leetcode Solution Series Max Area Island



トピックリンク： 695.島の最大面積

トピック：n * m 01行列を与え、行列内の連続する1が占める最大の面積を見つけます。連続とは、ユニットの上下左右に1つずつ存在する必要があることを意味します。



注意してください：

  1. 行列は必ずしも正方行列である必要はありません。長さを判断するときは、長さと幅に注意してください。
  2. 検索が境界を越えるときの状況に注意を払い、座標が妥当かどうかを判断します。
  3. 詳細検索を使用する場合、訪問した配列を使用して、検索されたかどうかを判断できます。これは、マトリックスの値を変更することで判断できます。

I.アルゴリズムの設計

明らかに、これは深い検索チャートの問題であり、合格することができます 図中の1を起点としてノードを検索し、上、下、左、右の方向で1があるかどうかを確認します。 1がある場合は、どれも見つからなくなるまで深さ検索を続けます。 、トラバーサルの数、つまり合計値を返します。



上、下、左、右のノードが1であるかどうかを判断するために、配列を初期化して4方向のベクトルを生成し、各ノードを4回トラバースし、範囲外かどうかに注意します。さらに、1が見つからない場合は、新しく追加されたベクトルを減算して、元の開始点に戻ることを忘れないでください。

次に、コードが実装されます

class Solution { public: int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}} int maxAreaOfIsland(vector<vector<int>>& grid) { int result = 0 for (int i = 0 i < grid.size() ++i) { for (int j = 0 j < grid[0].size() ++j) { if(grid[i][j] == 1){ int temp = dfs(i, j, grid) result = max(result, temp) } } } return result } int dfs(int x, int y, vector<vector<int>>& grid){ int sum = 1 grid[x][y] = 2 for (int i = 0 i < 4 ++i) { cout << 'first:' << x << ' ' << y << endl x += dir[i][0] y += dir[i][1] if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()){ x -= dir[i][0] y -= dir[i][1] continue } cout << x << ' ' << y << endl if(grid[x][y] == 1){ grid[x][y] = 2 sum += dfs(x,y,grid) cout << x << ' ' << y << ' ' << sum << endl } x -= dir[i][0] y -= dir[i][1] } return sum } }

第三に、改善方法

上記のアルゴリズムは96ミリ秒実行され、ランキングでさえそれほど恥ずべきことではありません。そこで、コードの最適化を開始しました。 4方向でノードにアクセスしたいので、ベクトルを前後に加算または減算する必要はありませんが、直接再帰的にアクセスします。

class Solution { public: int dfs(vector<vector<int>>& grid, int x, int y){ if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()) return 0 if (grid[x][y] == 1){ grid[x][y] = 2 return (1 + dfs(grid, x-1, y) + dfs(grid, x, y+1) + dfs(grid, x, y-1) + dfs(grid, x+1, y)) }else return 0 } int maxAreaOfIsland(vector<vector<int>>& grid) { int maxArea = 0 for(int i=0 i < grid.size() ++i) for (int j=0 j < grid[0].size() ++j){ // check if 1 is met, if yes, dfs and count the area if (grid[i][j] == 1) { // we will set those visited 1 as 2, so that we dont need to store a vector visited int area = dfs(grid, i, j) if (area > maxArea) maxArea = area } } return maxArea } }