C++で解く「上昇する水面を泳ぐ」問題（Swim in Rising Water）

問題概要

N×N のグリッドが与えられ、各マス grid[i][j] には地点 (i, j) の標高が格納されています。ここで雨が降り始めたとしましょう。時刻 t において、グリッド上のどこでも水深は一様に t になります。隣接する2つのマスの標高がどちらも t 以下であれば、その間を上下左右の4方向へ移動（泳ぐ）することができ、移動にかかる時間はゼロ、つまり条件さえ満たしていれば無限の距離を瞬時に進めるものとします。

スタート地点は左上の (0, 0) です。右下のマス (N-1, N-1) に到達できる最短の時刻を求めてください。

入力例

青色で示されたマスが最適な経路です。この場合の答えは 16 となります。

解き方（アルゴリズム）

この問題は、ダイクストラ法と同じ発想で効率よく解けます。「そのマスに到達するために必要な最低時刻＝そこまでの経路における最大標高」をコストとみなし、コストが小さいマスから優先的に展開していくのがポイントです。

• 時刻 time と座標 x、y を持つ構造体 Data を定義します。
• 4方向の移動を表す配列 dir（サイズ 4×2）:= {{1,0},{-1,0},{0,1},{0,-1}} を用意します。
• n := グリッドの行数、m := グリッドの列数 とします。
• 最小ヒープとして動作する優先度付きキュー q を定義します。
• 訪問管理用の n×m の2次元配列 visited を宣言し、すべて 0 で初期化します。
• visited[0][0] := 1 とします。
• Data(grid[0][0], 0, 0) を q に挿入します。
• q が空でない間、以下を繰り返します。
  • q の先頭要素を node として取り出し、キューから削除します。
  • time := node.time、x := node.x、y := node.y とします。
  • x == n-1 かつ y == m-1 であれば、time を返します（ゴール到達）。
  • i := 0 から i < 4 の範囲で以下を繰り返します。
    • nx := dir[i][0] + x、ny := dir[i][1] + y とします。
    • nx と ny がグリッドの範囲内かつ未訪問であれば、visited[nx][ny] := 1 とし、Data(max(grid[nx][ny], time), nx, ny) を q に挿入します。
• ループを抜けた場合は -1 を返します。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
struct Data{
    int time, x, y;
    Data(int a, int b, int c){
        time = a;
        x = b;
        y = c;
    }
};
struct Comparator{
    bool operator()(Data a, Data b){
        return !(a.time < b.time);
    }
};
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        priority_queue <Data, vector <Data>, Comparator> q;
        vector < vector <int> > visited(n, vector <int>(m, 0));
        visited[0][0] = 1;
        q.push(Data(grid[0][0], 0, 0));
        while(!q.empty()){
            Data node = q.top();
            q.pop();
            int time = node.time;
            int x = node.x;
            int y = node.y;
            if(x == n - 1 && y == m - 1) return time;
            for(int i = 0; i < 4; i++){
                int nx = dir[i][0] + x;
                int ny = dir[i][1] + y;
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]){
                    visited[nx][ny] = 1;
                    q.push(Data(max(grid[nx][ny], time), nx, ny));
                }
            }
        }
        return -1;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> v = {{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},{10,9,8,7,6}};
    cout << (ob.swimInWater(v));
}

入力

{{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},{10,9,8,7,6}}

出力

16

計算量

各マスは高々1回ずつキューに追加されるため、優先度付きキューの操作を含めた全体の時間計算量は O(N² log N)、訪問管理配列などに必要な空間計算量は O(N²) となります。グリッドのサイズが大きくなっても十分に実用的なアプローチです。