C++で解く「異なる島の数 II」問題

問題概要

空でない2次元バイナリ配列 grid が与えられます。ここでいう「島」とは、上下左右の4方向に連結した 1（陸地を表す）の集合のことであり、グリッドの四辺はすべて水に囲まれているものと仮定します。

求めるのは異なる島の数です。ある島が別の島と同じとみなされるのは、両者が同じ形状である場合、または90度・180度・270度のいずれかで回転した後、あるいは左右方向・上下方向のいずれかで反転した後に同じ形状になる場合です。

例として、入力が次のようなケースを考えます。

この場合の出力は 1 になります。左上のL字形の島と右下のL字形の島は、回転させると同じ形になるため、同一の島としてカウントされるからです。

解法の考え方

まずDFSで各島を構成するセルの座標を収集し、その座標に対して回転・反転による8通りの変形をすべて生成します。それぞれをソートして平行移動により正規化（正準形への変換）すれば、位置や向きに依存しない「形状の指紋」が得られます。この正準形どうしを比較することで同一形状の島を判定でき、set に格納すれば重複を自動的に排除できます。

具体的な手順は以下の通りです。

• マップ m を1つ定義します。
• 関数 dfs() を定義します。引数は i、j、grid、idx です。
  • i または j がグリッドの範囲外にある場合、もしくは grid[i][j] が 0 の場合は return します。
  • grid[i][j] := 0 とします（訪問済みマーク）。
  • m[idx] の末尾に { i, j } を挿入します。
  • dfs(i + 1, j, grid, idx) を呼び出します。
  • dfs(i - 1, j, grid, idx) を呼び出します。
  • dfs(i, j - 1, grid, idx) を呼び出します。
  • dfs(i, j + 1, grid, idx) を呼び出します。
• 関数 norm() を定義します。座標配列 v を引数に取ります。
  • ペアの2次元配列 s（8行）を定義します。
  • i := 0 から v のサイズ未満まで繰り返します。
    • x := v[i].first、y := v[i].second とします。
    • s[0] の末尾に { x, y } を挿入します。
    • s[1] の末尾に { x, -y } を挿入します。
    • s[2] の末尾に { -x, y } を挿入します。
    • s[3] の末尾に { -x, -y } を挿入します。
    • s[4] の末尾に { y, x } を挿入します。
    • s[5] の末尾に { y, -x } を挿入します。
    • s[6] の末尾に { -y, x } を挿入します。
    • s[7] の末尾に { -y, -x } を挿入します。
  • i := 0 から s のサイズ未満まで繰り返し、各行 s[i] をソートします。
  • 再度 i := 0 から s のサイズ未満まで繰り返します。
    • j := 1 から v のサイズ未満まで繰り返し、s[i][j].first から s[i][0].first を、s[i][j].second から s[i][0].second を減算します（平行移動による正規化）。
    • s[i][0].first := 0、s[i][0].second := 0 とします。
  • s 全体をソートします。
  • s[0] を返します（辞書順最小の正準形）。
• メイン処理では以下を行います。
  • セット pts を1つ定義します。
  • cnt := 1 とします。
  • i := 0 から grid のサイズ未満まで、j := 0 から grid[0] のサイズ未満まで二重ループします。
    • grid[i][j] が 1 の場合：
      • cnt を1増やします。
      • dfs(i, j, grid, cnt) を呼び出します。
      • norm(m[cnt]) を pts に挿入します。
• pts のサイズを返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map < int, vector < pair <int, int> > > m;
   void dfs(int i, int j, vector < vector <int> >& grid, int idx){
      if (i >= grid.size() || j >= grid[0].size() || i < 0 || !grid[i][j])
         return;
      grid[i][j] = 0;
      m[idx].push_back({ i, j });
      dfs(i + 1, j, grid, idx);
      dfs(i - 1, j, grid, idx);
      dfs(i, j - 1, grid, idx);
      dfs(i, j + 1, grid, idx);
   }
   vector < pair <int, int> > norm(vector < pair < int, int > > v){
      vector<vector<pair<int, int> > > s(8);
      for (int i = 0; i < v.size(); i++) {
         int x = v[i].first;
         int y = v[i].second;
         s[0].push_back({ x, y });
         s[1].push_back({ x, -y });
         s[2].push_back({ -x, y });
         s[3].push_back({ -x, -y });
         s[4].push_back({ y, x });
         s[5].push_back({ y, -x });
         s[6].push_back({ -y, x });
         s[7].push_back({ -y, -x });
      }
      for (int i = 0; i < s.size(); i++) {
         sort(s[i].begin(), s[i].end());
      }
      for (int i = 0; i < s.size(); i++) {
         for (int j = 1; j < v.size(); j++) {
            s[i][j].first = s[i][j].first - s[i][0].first;
            s[i][j].second = s[i][j].second - s[i][0].second;
         }
         s[i][0].first = 0;
         s[i][0].second = 0;
      }
      sort(s.begin(), s.end());
      return s[0];
   }
   int numDistinctIslands2(vector<vector<int>>& grid) {
      set<vector<pair<int, int> > > pts;
      int cnt = 1;
      for (int i = 0; i < grid.size(); i++) {
         for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {
               cnt++;
               dfs(i, j, grid, cnt);
               pts.insert(norm(m[cnt]));
            }
         }
      }
      return pts.size();
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}};
   cout << (ob.numDistinctIslands2(v));
}

入力

{{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1}}

出力

1

計算量の目安

グリッドのサイズを R×C、各島のセル数を K とすると、DFSによる全島の探索は O(R×C)、各島ごとの正規化は8通りの変形それぞれにソート O(K log K) が必要です。したがって全体の計算量は O(R×C×K log K) 程度となり、グリッドがそれほど大きくなければ十分実用的な速度で動作します。