グリッド上でのダイクストラ法

グリッド上でのダイクストラ法について自分が詰まってしまったので誰かの役に立てばと思い載せておきます。
### どんな問題に使えるのか
- [yukicoder No.20 砂漠のオアシス](https://yukicoder.me/problems/no/20)  
- [PAST(第一回アルゴリズム実技検定 J 問題)](https://atcoder.jp/contests/past201912-open/tasks/past201912_j)

### 普通のダイクストラ法との違いは？
```cpp
using P = pair<int, int>;

struct edge {
    int to;
    int cost;
};

vector<int> dist;
vector<vector<edge> > g;

void dijkstra(int s) {
    dist = vector<int>(n, Inf);
    dist[s] = 0;
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P(0, s));

    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if (dist[v] < p.first) continue;

        rep (i, g[v].size()) {
            edge e = g[v][i];
            if (dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost;
                pq.push(P(dist[e.to], e.to));
            }
        }
    }
}
```
これが自分が普段使っているダイクストラのコードです。  

```cpp
using P = pair<int, int>;
using PP = pair<int, P>;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

vector<vector<int> > g, dist;

void dijkstra(int sx, int sy) {
    dist = vector<vector<int> >(h, vector<int>(w, Inf));
    dist[sx][sy] = 0;
    priority_queue<PP, vector<PP>, greater<PP> > pq;
    pq.push(PP(0, P(sx, sy)));

    while (!pq.empty()) {
        PP p = pq.top();
        pq.pop();
        int c = p.first;
        int vx = p.second.first, vy = p.second.second;

        rep (i, 4) {
            int nx, ny;
            nx = vx + dx[i], ny = vy + dy[i];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            if (dist[nx][ny] <= g[nx][ny] + c) continue;
            dist[nx][ny] = g[nx][ny] + c;
            pq.push(PP(dist[nx][ny], P(nx, ny)));
        } 
    }
}
```

そしてこれが PAST の J 問題で使った グリッド上でのダイクストラのコードです。
大きな違いとしては  

- struct edge を使うよりも 2 次元配列としてグラフを持つ方が楽  
- 各地点へのコストを表す配列 (上記のコードでは dist) が 1 次元から 2 次元に変わっていること 
- pairのネスト構造を使用している  

です。  
### ちょっとしたプログラムの解説
1. **各地点へのコストを表す配列が 2 次元なわけ**  
グリッド上では各地点が x 座標、y 座標の 2 点で表されます。  
そのため dist[x][y] = cost で、ダイクストラの開始地点から座標 (x, y) へのコストを表しています。  
2. **priority_queue にどんな形の値を入れているか**  
第一引数に注目していただければわかるのですが、pair のネスト形で値が入っていきます。  
2 つ目の pair<int, int> で座標 (x, y) を、1 つ目の int に座標 (x, y) へのコストを入れています。

### グリッド上ダイクストラでの経路復元
もちろん経路復元もできます。

```cpp
using P = pair<int, int>;

struct edge {
    int to;
    int cost;
};

vector<int> dist, pre;
vector<edge> g;

void dijkstra(int s) {
    pre = vector<int>(n, -1);
    dist = vector<int>(n, Inf);
    dist[s] = 0;
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P(0, s));

    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if (dist[v] < p.first) continue;

        rep (i, g[v].size()) {
            edge e = g[v][i];
            if (dist[e.to] > dist[v] + e.cost) {
                dist[e.to] = dist[v] + e.cost;
                pq.push(P(dist[e.to], e.to));
            }
        }
    }
}

vector<int> restore(int t) {
    vector<int> path;
    for (; t != -1; t = pre[t]) path.push_back(t);
    reverser(path.begin(), path.end());

    return path;
}
```  

この普段のダイクストラでの経路復元に対し、

```cpp
using P = pair<int, int>;
using PP = pair<int, P>;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

vector<vector<int> > g, dist;
vector<vector<P> > pre;

void dijkstra(int sx, int sy) {
    dist = vector<vector<int> >(h, vector<int>(w, Inf));
    pre = vector<vector<P> >(h, vector<P>(w, P(-1, -1)));
    dist[sx][sy] = 0;
    priority_queue<PP, vector<PP>, greater<PP> > pq;
    pq.push(PP(0, P(sx, sy)));

    while (!pq.empty()) {
        PP p = pq.top();
        pq.pop();
        int c = p.first;
        int vx = p.second.first, vy = p.second.second;

        rep (i, 4) {
            int nx, ny;
            nx = vx + dx[i], ny = vy + dy[i];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            if (dist[nx][ny] <= g[nx][ny] + c) continue;
            dist[nx][ny] = g[nx][ny] + c;
            pre[nx][ny] = P(vx, vy);
            pq.push(PP(dist[nx][ny], P(nx, ny)));
        } 
    }
}

vector<P> restore(int tx, int ty) {
    vector<P> path;
    int x, y;
    for (; tx != -1 || ty != -1; tx = pre[x][y].first, ty = pre[x][y].second) {
        path.push_back(P(tx, ty));
        x = tx, y = ty;
    }
    reverse(path.begin(), path.end());

    return path;
}
```
というようになります。
基本的には通常ダイクストラの応用ですが、for 文の変化式 (3つ目) で、以下のように書いてしまうとバグります。
(更新された tx の値が ty の値の取得に使用されてしまうため) 
 
```cpp
vector<P> restore(int tx, int ty) {
    vector<P> path;
    for (; tx != -1 || ty != -1; tx = pre[tx][ty].first, ty = pre[tx][ty].second) {
        path.push_back(P(tx, ty));
    }
    reverse(path.begin(), path.end());

    return path;
}
```

### 終わり
ここまでで記録しておきたかったことは終わりです。 
もし何かの役に立てば幸いです。