AGC007 A - Shik and Stone - ペンギンかっこいい

備忘録

問題

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
# MOD = 998244353
INF = float('inf')


def dfs(A, h, w, H, W, ch, cw):
    move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    cnt = 0
    for nh, nw in move:
        if nh == -1 and ch:
            continue
        if nw == -1 and cw:
            continue
        if 0 <= h + nh < H and 0 <= w + nw < W and A[h + nh][w + nw] == '#':
            cnt += 1
    if cnt > 1:
        return

    if h+1 == H and w+1 == W and cnt == 0:
        A[-1][-1] = 'G'
        return

    if h + 1 < H and A[h+1][w] == '#':
        dfs(A, h + 1, w, H, W, True, False)
    if w + 1 < W and A[h][w+1] == '#':
        dfs(A, h, w + 1, H, W, False, True)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    A = []
    for _ in range(H):
        a = list(iss())
        A.append(a)

    dfs(A, 0, 0, H, W, False, False)
    print('Possible' if A[-1][-1] == 'G' else 'Impossible')


if __name__ == '__main__':
    main()

考え方

ケース数が少ないため、愚直にDFSを行いました。

条件を満たさない移動が発生するケースは以下の3通りです。
1. スタート地点から移動可能なマスが2つ以上存在する
2. スタートからゴールまでの経路で、移動可能なマスが３つ以上存在する地点がある
3. ゴール地点から移動可能なマスが2つ以上存在する

愚直に上または左から来たことを示すフラグを引数に用意して、
全ての条件を満たす場合のみ移動を行うことで、ゴールに到達可能か否か判定します。

公式の解説を参考に以下の回答も通しました。

import sys
import os
import collections

def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def iss(): return sys.stdin.buffer.readline().decode().rstrip()

def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    cnt = 0
    for _ in range(H):
        count = collections.Counter(iss())
        cnt += count['#']
    print('Possible' if cnt == (H + W - 1) else 'Impossible')


if __name__ == '__main__':
    main()

移動可能な方向は右または下だけです。
つまり左上から右下まで最短ルートで移動するため、
移動する数は必ずW + H - 1回だけになります。
そのため、#の数がW + H - 1回以上存在する場合には、不要な移動が発生しているとみなすことが出来ます。