問題
グリッド上で一直線に並んだ k 個のマスの並びを考えます。向きは、行に沿って左から右、列に沿って上から下、または2方向の斜めのいずれかです。並びに含まれる数を掛け合わせ、積が最大になる並びを見つけてください。
largest_product_in_grid(grid, k) を実装してください。
入力
grid:数が並んだ長方形のグリッド。どの行も同じ長さです。
k:並びの長さ。
出力
長さ k のすべての並びについて、積の最大値を返してください。どの方向にも長さ k の並びがグリッドに収まらない場合は、0 を返します。
制約
1 ≤ 行数, 列数 ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5
例
入力:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 2
期待される出力:
expected = 72
入力:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 2;
期待される出力:
long long expected = 72;
入力:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 2;
期待される出力:
long expected = 72;
解説
最良の並びは最下行の 8 と 9 で、8 × 9 = 72 です。斜めの 5, 9 では 45 にしかなりません。
入力:
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
k = 3
期待される出力:
expected = 504
入力:
std::vector<std::vector<long long>> grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
long long k = 3;
期待される出力:
long long expected = 504;
入力:
long[][] grid = new long[][] {
new long[] {1, 2, 3},
new long[] {4, 5, 6},
new long[] {7, 8, 9}
};
long k = 3;
期待される出力:
long expected = 504;
解説
最下行の 7 × 8 × 9 = 504 が、右端の列の 3 × 6 × 9 = 162 やどの斜めよりも大きくなります。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
方向は右、下、右下、左下の4つで十分です。それ以外は同じ並びを逆にたどるだけです。
ヒント 2
各開始マスから、並びの最後のマスがまだグリッド内にあるかを確認します。
ヒント 3
0 を返すのは、長さ k の並びが1つも収まらないときだけです。
目安の計算量
時間 O(rows × cols × k)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。