グリッド版ダイクストラ問題セットなのですが、C#の解説がありません。そこで自分で解説をつくることにしました。

コストの合計の最小値

グリッド状の盤面で上下左右の移動を繰り返して、左上から右下まで移動するときに通るマスのコストの合計の最小値を求めよ。

入力例

0 3 1 4 1 5
9 2 6 5 3 5
3 9 7 9 3 2

出力例 17

下記のコードで経路復元の問題とゴールのマスが複数の問題も解くことができます。

1つの中継点がある問題

1つの中継点がある問題では上記をメソッドにして複数回呼び出せば定められた中継点をとおってコストの合計値の最小値を求めることができます。

左上からスタートして右上のマスを経由して右下のゴールまで移動するときのコストの合計の最小値なら以下の方法で取得できます。

マスのコストを0にできるチケット

上下左右の移動を繰り返して左上から右下まで移動するときに通るマスのコストの合計の最小値を求めよ。ただし1 つのマスのコストを 0 にできるチケットを n 枚使うことができる。このチケットはスタート、ゴールを含む全てのマスに対して使うことができる。

残りチケットの枚数でコストを格納できるようにする。

経由地の最大コストの最小値

左上から右下まで通るマスのコストの最大値が最小になるような経路で移動し、そのコストの最大値を出力せよ。

コストの計算方法を変えるだけ。ループのなかで costs[row, col], map[newRow, newCol]のうち大きい方をコストとして、これが移動先のコスト小さい場合は書き換えます。ゴールに到達したときのコストが求めるべき答えとなります。