paizaラーニング問題集「陣取りゲーム」を解いてみた

▼問題

▼考え方

この問題を解くために私が考えた内容1～3を以下に示します。

[概要]
AおよびBが勝ち取ったマスの座標は、1つずつ[y,x]で表現し、リストAおよびBで管理します。以下に例を示します。最終的にリストの要素数が多かったほうが勝ちです。

陣取りゲーム前
A = [[0, 0]]
B = [[2, 2]]
↓
陣取りゲーム後
A = [[0, 0], [1, 0], [0, 1], [0, 2], [1, 1], [2, 0]]
B = [[2, 2], [1, 2], [2, 1]]

また、マス全体の情報をリストSで管理します。Aが勝ち取ったマスは"A"、Bが勝ち取ったマスは"B"、障害物のマスは"#"、誰の陣地でもないマスは"."です。AとBが勝ち取れるマスは"."のマスのみです。

陣取りゲーム前
S = [['A', '.', '.'], ['.', '.', '.'], ['.', '.', 'B']]
↓
陣取りゲーム後
S = [['A', 'A', 'A'], ['A', 'A', 'B'], ['A', 'B', 'B']]

1. 盤面の情報を1行ずつ読み込みます。読み込みつつ、AとBの最初のマスの座標を得ます。

2. AとBの先攻後攻の情報は、リストSQ(sequence)で管理します。

3. 題意のようにAとBの操作を行います。while文を用いて、AとBのどちらかの操作が可能な間は操作を継続します。例えば"Aの次の操作が可能"とは、Aの操作前のリストAの要素数(変数Al)が、Aの操作後に増加したということです。

3.1.
Aの操作前のリストAの要素数、Bの操作前のリストBの要素数をそれぞれ得ます。

3.2.
SQ[0]の文字が先行、SQ[1]の文字が後攻です。

3.3.
前回の操作でAおよびBが勝ち取ったマスの座標を全て関数Get_udlr_Posに渡して、そのマスの上下左右のマスの座標を求めます。前回の操作で勝ち取ったマスの座標は、リストAを変数ASと変数AFで指定します。

3.3.1.
重複した場合は、それを排除します。（排除しないと座標の数が膨大になり、タイムオーバーしてしまいます。）

3.4.
誰の陣地でもないマス（"."）だった場合は、そのマスを勝ち取れます。勝ち取ったマスはリストAに追加します。

3.5.
前回の操作で勝ち取ったマスの座標を管理する変数AS,AFを更新します。

▼コード

############### 関数処理 ###############

# Get_udlr_Pos: 渡された上下左右のマスの座標を求める関数
def Get_udlr_Pos(XY):

    # udlr_pos: 求めた上下左右のマスの座標を一時的に格納するリスト
    udlr_pos = []
    
    for i in range(len(XY)):
        
        if XY[i][0]-1 >= 0:
            udlr_pos.append([XY[i][0]-1,XY[i][1]])
        if XY[i][0]+1 <= H-1:
            udlr_pos.append([XY[i][0]+1,XY[i][1]])
        if XY[i][1]-1 >= 0:
            udlr_pos.append([XY[i][0],XY[i][1]-1])
        if XY[i][1]+1 <= W-1:
            udlr_pos.append([XY[i][0],XY[i][1]+1])

    # 考え方3.3.1.
    udlr_pos = list(map(list, set(map(tuple,udlr_pos))))
    
    return udlr_pos

############### メイン関数処理 ###############

H,W = map(int,input().split())

N = input()

A = []
B = []
S = []

# 考え方1.
for i in range(H):

    # S_c: 盤面の情報を1行ずつ読み込み、それを格納するリスト
    S_c = list(input())
    
    S.append(S_c)
    
    if "A" in S_c:
        A.append([i,S_c.index("A")])
    if "B" in S_c:
        B.append([i,S_c.index("B")])

# 考え方2.
if N == "A":
    # SQ: 先攻後攻を格納するリスト
    SQ = [N,"B"]
else:
    SQ = [N,"A"]

# 考え方3.

# Al: Aの操作前のリストAの要素数
Al = 0
# Bl: Bの操作前のリストBの要素数
Bl = 0
# AS: Aの前回の操作で勝ち取ったマスの、リストA上の開始位置
AS = 0
# AF: Aの前回の操作で勝ち取ったマスの、リストA上の終了位置
AF = len(A)
# BS: Bの前回の操作で勝ち取ったマスの、リストB上の開始位置
BS = 0
# BF: Bの前回の操作で勝ち取ったマスの、リストB上の終了位置
BF = len(B)

while(Al < len(A) or Bl < len(B)):

    # 考え方3.1.
    Al = len(A)
    Bl = len(B)

    # 考え方3.2.
    for i in range(2):
        
        if SQ[i] == "A":

            # 考え方3.3.
            # checkpos: 前回の操作でAおよびBが勝ち取ったマスの、上下左右のマスの座標を格納するリスト
            checkpos = Get_udlr_Pos(A[AS:AF+1])

            # 考え方3.4.
            for j in range(len(checkpos)):
                if S[checkpos[j][0]][checkpos[j][1]] == ".":
                    S[checkpos[j][0]][checkpos[j][1]] = "A"
                    A.append(checkpos[j])

            # 考え方3.5.
            AS = AF
            AF = len(A)

        else:
            
            checkpos = Get_udlr_Pos(B[BS:BF+1])
            
            for j in range(len(checkpos)):
                if S[checkpos[j][0]][checkpos[j][1]] == ".":
                    S[checkpos[j][0]][checkpos[j][1]] = "B"
                    B.append(checkpos[j])
                    
            BS = BF
            BF = len(B)
            
print(len(A),len(B))
if len(A) > len(B):
    print("A")
else:
    print("B")