【電脳少女プログラミング2088 ー壊レタ君を再構築ー】一番通りの繁華街（paizaランク：B相当）解説

はじめに

この記事では、「一番通りの繁華街」の問題を通して、コードを作成するまでの思考順序を解説しています。

問題文

設定

あなたはギャングの縄張りの争いについてギャングから話を聞いています。
ギャングは自分たちのアジトの建物どうしを線で繋いだ時に正方形になる地域を自分たちの縄張りとすることにする取り決めをしています。また、縄張りとなる正方形の各辺は地域の情報の縦もしくは横に並行となるものとし、斜めは含まないものとします。
N × N の広さの地域の中にはギャングのアジトの建物が N 箇所あります。
縄張りがいくつあるか出力してください。

入力例を用いた説明

入力例1 では、座標の原点を左上(1,1)とした場合、

• (1,1), (1, 3), (3, 1), (3, 3) の建物
• (1,1), (1, 5), (5, 1), (5, 5) の建物
• (1,3), (1, 5), (3, 3), (3, 5) の建物

のようにアジトの建物が正方形をなしている場所が 3 つあります。縄張りは 3 つあるので 3 を出力します。

• 建物の組み合わせが異なる場合、異なる縄張りであること
• 縄張りの中に縄張りがあるような場合も 1 つと数えること

に注意してください。

入力される値

入力は標準入力にて以下のフォーマットで与えられます。
N
r_1
r_2
…
r_N

• 1 行目に地域の大きさを表す整数 N が与えられます
• 続く 2 行目から N+1 行目まで地域の情報を表す長さ N の文字列 r_i (1 ≦ i ≦ N) が与えられます
  • r_{i, j} = '#' (1 ≦ i, j ≦ N) のとき、その場所はなにもないことを表す
  • r_{i, j} = '.' (1 ≦ i, j ≦ N) のとき、その場所はアジトの建物であることを表す
• 入力は合計で N+1 行となり、末尾に改行が 1 つ入ります

条件

• 5 ≦ N ≦ 50
• r_i (1 ≦ i ≦ N) は N 文字
• r_i (1 ≦ i ≦ N) は # もしくは . からなる

期待する出力

以下の形式で、出力してください。
縄張りがいくつあるか出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。

入力例1

入力
5
.#.#.
#####
.#.#.
##.##
.###.

出力
3

入力例2

入力
5
.....
.....
.....
.....
.....

出力
30

解答コード

この問題をPythonコードで解答すると、自分の場合は以下のようになりました。
このコードで得点は100点だったので、問題はないと思います。

answer.py

# 地域のデータを格納
area_data = []

# 出力する正方形の数
square_num = 0

# 標準入力から地域のデータを2次元リストで受取
input_line = int(input())
for i in range(input_line):
    area_data.append(list(input().rstrip()))

# side_length:現在調べている正方形の辺の長さ
for side_length in range(1,input_line):
    # axis1:現在調べている地域の1次元目の基準座標
    for axis1 in range(input_line):
        # axis2:現在調べている地域の2次元目の基準座標
        for axis2 in range(input_line):
            # インデックスの範囲内の場合
            if (axis1 + side_length < input_line) and (axis2 + side_length < input_line):
                if area_data[axis1][axis2] == '#':
                    continue
                if area_data[axis1][axis2 + side_length] == '#':
                    continue
                if area_data[axis1+side_length][axis2] == '#':
                    continue
                if area_data[axis1+side_length][axis2 + side_length] == '#':
                    continue
                square_num += 1
            else:
                continue

print(square_num)

解説

部分ごとに解答コードの解説を行います。

入出力用変数の宣言

answer.py

# 地域のデータを格納
area_data = []

# 出力する正方形の数
square_num = 0

標準入力から与えられる地域の座標データを格納するための変数をarea_dataという名前で宣言し、題意に相当する出力する正方形の数をsquare_numという変数で宣言しています。

標準入力の受取

answer.py

# 標準入力から地域のデータを2次元リストで受取
input_line = int(input())
for i in range(input_line):
    area_data.append(list(input().rstrip()))

このコードは以下のように動作します。

• 地域の大きさNを標準入力から整数値として受け取り、input_lineに代入
• 長さNの文字列r_i(1 ≦ i ≦ N) をinput_lineの数だけ標準入力からリストとして受け取り、area_dataに追加

list(input().rstrip())の部分は文字列として受け取ったr_iをリストに変換しています。
例：文字列'.#.#.'が入力された場合、リスト['.','#','.','#','.']に変換される。
リストに変換したものをリストに追加することで、2次元リストを作成しています。

出力する正方形の数のカウントと出力

この問題を考えるための思考順序を以下に示します。
この問題を一言で言うと「正方形をカウントする問題」です。
したがって、数えるべきすべての正方形の情報が特定できれば問題クリアと言えます。
ここで注目するべきは、「なんの数値を規定すれば数えるべき正方形が特定できるか？」です。
それは以下の3つの数値であると言えます。

• 調査対象の正方形の辺の長さ
• 調査対象の地域のx座標
• 調査対象の地域のy座標

※ここでは分かりやすさのため、座標を「x座標、y座標」と表現しましたが、コードで言うところの正しい表現は、area_dataの「1次元目、2次元目」であり、この「1次元目、2次元目」が「x座標、y座標」に相当します。

したがって、この3つの数字を3重ループのfor文で回すと、調査すべきすべての正方形を数えることができます。

【例】 地域の大きさが5の場合の各数値が取りうる値

※調査対象の座標は、area_dataのインデックス番号として表記しています。

• 調査対象の正方形の辺の長さ -> 1,2,3,4
• 調査対象の地域のx座標 -> 0,1,2,3,4
• 調査対象の地域のy座標 -> 0,1,2,3,4

したがって、変数を用いて一般化すると、以下のようになります。

• 調査対象の正方形の辺の長さ -> 1からinput_line未満まで
• 調査対象の地域のx座標 -> 0からinput_line未満まで
• 調査対象の地域のy座標 -> 0からinput_line未満まで

以上のことを踏まえると、以下のような3重ループができあがります。

answer.py

# side_length:現在調べている正方形の辺の長さ
for side_length in range(1,input_line):
    # axis1:現在調べている地域の1次元目の基準座標
    for axis1 in range(input_line):
        # axis2:現在調べている地域の2次元目の基準座標
        for axis2 in range(input_line):

正方形の数を数える際の注意点

今回、for文で回すことを考えた場合、地域を以下のようなルートで回ることになります。
ただし、図に示しているのは基準座標のルートであり、この座標を起点として、正方形が作成できるかどうかを「調査対象の辺の長さ」の条件を満たした最も近い3座標も調べることで、判別します。

正方形を作る場合は必ず4点を通るわけなので、この4点がすべて地域の大きさの範囲内に収まる必要があります。したがって、for文内の処理の最初の段階で、調査する座標がインデックスの範囲内であるかどうかを調べる必要があります。すなわち、「基準座標に調査対象の正方形の辺の長さを加えたものがinput_lineを超えないか」を調べるということです。よって、条件文は以下のようになり、これを満たす場合に限って、正方形が作成できるかの調査を行います。

answer.py

# インデックスの範囲内の場合
if (axis1 + side_length < input_line) and (axis2 + side_length < input_line):

正方形をカウントするか否かの分岐

ここで、メインの条件である正方形をカウントする場合の条件を考えます。
正方形をカウントする条件は、調査対象の4つの座標（正方形の頂点）がすべて'#'でない場合です。よって、以下の条件をすべて満たさない場合、正方形をカウントします。

• area_data[axis1][axis2] == '#'
• area_data[axis1][axis2 + side_length] == '#':
• area_data[axis1+side_length][axis2] == '#':
• area_data[axis1+side_length][axis2 + side_length] == '#':

すなわち、これらのいずれかの条件を満たした場合は、for文を次に進め、すべて満たさない場合は、正方形をカウントするということです。continueを使うことで、for文を次に進めることができます。
以上のことを踏まえてコードを作成すると、解答コードが完成します。

まとめ

今回のようなコードを作成する際は、以下の3点を考えます。

• 調査対象の正方形を特定する数値何か
• 考慮すべき条件は何か
• 正方形をカウントする条件は何か

これらの問いを適切に解答していくことにより、コードを完成させることができます。