ABC258 B - Number Box Python解答例

AtCoder Beginner Contest 258 B - Number BoxをPythonで解きます。

問題

問題文をAtCoderのページより引用します。

問題文

正整数$N$が与えられます。

$N$行$N$列のマス目があり、上から$i$行目、左から$j$列目のマスには数字$A_{i,j}$が書かれています。

このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。

• $(1,i)$の上のマスは$(N,i)$であり、$(N,i)$の下のマスは$(1,i)$である。$(1\le i\le N)$
• $(i,1)$の左のマスは$(i,N)$であり、$(i,N)$の右のマスは$(i,1)$である。$(1\le i\le N)$

高橋君は、上下左右および斜めの$8$方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に$1$マス移動することを$N-1$回繰り返します。

高橋君は$N$個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。

制約

• $1 \le N \le 10$
• $1 \le A_{i,j} \le 9$
• 入力はすべて整数。

解答例

全探索

始点と方向を全探索します。
進む向きと開始するマスを決め打ちし、そこから$N$マス進み、通ったマスに書かれていた数字を記録します。それを整数として結合し、最大値を全探索すればよいです。

マスは上下左右が繋がっているため、全探索の途中でインデックスが範囲からはみ出ないように処理することだけ忘れないようにしましょう。

Pythonでの実装例を以下に示します。

b.py

from typing import List
import itertools


def main():
    # 入力受け取り
    N: int = int(input())
    # マス目は文字列のリストのリストとして受け取っておく。
    grid: List[List[int]] = [list(input()) for i in range(N)]

    answer: int = 0
    # dr、dcは各方向におけるインデックスの増加量。上下左右斜めの8通りに対応する。
    for dr, dc in zip([0, -1, -1, -1, 0, 1, 1, 1], [1, 1, 0, -1, -1, -1, 0, 1]):
        # 始点の全探索
        for i, j in itertools.product(range(N), range(N)):
            # 進む最中のインデックス
            r: int = i
            c: int = j
            # 通ったマスの数字を記録しておくリスト
            result: List[int] = []

            # N回進む
            for _ in range(N):
                # 現在地の数字を記録する
                result.append(grid[r][c])

                # インデックスを進める。
                r += dr
                # 負の値になったらNを足す。
                if r < 0:
                    r += N
                # Nを超えないように余りを取る。
                r %= N
                # 上に同じ
                c += dc
                if c < 0:
                    c += N
                c %= N

            # 最大値を取る。数字の記録リストを逆転させ、結合した文字列を整数に直している。
            answer = max(answer, int("".join(reversed(result))))

    # 答えの出力
    print(answer)


if __name__ == "__main__":
    main()

実際に提出したコードはこちら。