問題
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
例
例 1
入力：
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 です。
例 2
入力：
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 です。
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。