問題
A* はゲームやロボット工学で使われる代表的な経路探索アルゴリズムです。f = g + h の小さい順にセルを探索します。g はここまでに払ったコスト、h は残りのコストのヒューリスティックな見積もりです。
グリッドには各セルのコストが入っています。セルに入るとその値のコストがかかり、0 は入れない壁です。start から出発し (このセルのコストは払いません)、上下左右に移動できます。
ヒューリスティックとしてマンハッタン距離 |row - goal_row| + |col - goal_col| を使った A* を使ってください。通れるセルのコストはすべて 1 以上なので、このヒューリスティックは過大評価にならず、A* は最適な答えを返します。
a_star_cost(grid, start, goal) を実装してください。
入力
grid: セルのコストの行列 (0 = 壁)。
start, goal: [row, col] 形式の位置。
出力
goal に到達する最小の合計コストを返します。到達できない場合 (start または goal が壁の場合を含む) は -1 を返します。
制約
1 ≤ 行数, 列数 ≤ 100
0 ≤ 各コスト ≤ 9
例
入力：
goal = [2, 2]
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
start = [0, 0]
期待される出力：
expected = 4入力：
std::vector<long long> goal = {2, 2};
std::vector<std::vector<long long>> grid = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
std::vector<long long> start = {0, 0};
期待される出力：
long long expected = 4;入力：
long[] goal = new long[] {2, 2};
long[][] grid = new long[][] {
new long[] {1, 1, 1},
new long[] {1, 0, 1},
new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
期待される出力：
long expected = 4;解説
中央は壁です。右に 2 回、下に 2 回 (または下から右) 進むとコスト 1 のセルに 4 回入るので、合計 4 です。
入力：
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
期待される出力：
expected = 6入力：
std::vector<long long> goal = {0, 2};
std::vector<std::vector<long long>> grid = {
{1, 9, 1},
{1, 9, 1},
{1, 1, 1}
};
std::vector<long long> start = {0, 0};
期待される出力：
long long expected = 6;入力：
long[] goal = new long[] {0, 2};
long[][] grid = new long[][] {
new long[] {1, 9, 1},
new long[] {1, 9, 1},
new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
期待される出力：
long expected = 6;解説
9 をまっすぐ横切ると 9 + 1 = 10 かかります。下に降りて最下行を進み、また上がるとコスト 1 のセルに 6 回入るので、合計 6 です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
移動コストとゴールまでの Manhattan 距離の合計で優先順位付けする priority queue を使います。
ヒント 2
各 cell についてこれまでの最良コストを記録し、この経路で改善したときだけその cell を展開します。
ヒント 3
壁や、開始セルまたはゴールセルが塞がれている場合は不可能として扱い、開始セルに入るコストは 0 だと覚えておきます。
目安の計算量
時間 O(rows * cols log(rows * cols))、追加メモリ O(rows * cols)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。