結果

問題 No.2412 YOU Grow Bigger!
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:44:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,089 ms / 6,000 ms
コード長 3,034 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 97,076 KB
最終ジャッジ日時 2025-03-31 17:45:26
合計ジャッジ時間 23,819 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        grid.append(list(sys.stdin.readline().strip()))
    
    start = (0, 0)  # (i, j) of top-left of 3x3 block. So area is (i, j, i+2, j+2)
    end = (H-3, W-3)

    # Precompute original spikes and allowed cells
    # Start region: rows 0-2, cols 0-2 (assuming 0-based)
    # End region: rows H-3 to H-1, cols W-3 to W-1 (0-based)
    def is_start_region(r, c):
        return r < 3 and c < 3
    def is_end_region(r, c):
        return r >= H-3 and c >= W-3
    allowed_cells = []
    for r in range(H):
        for c in range(W):
            if grid[r][c] == '.' and not is_start_region(r, c) and not is_end_region(r, c):
                allowed_cells.append((r, c))
    
    # Check if a position (i, j) (top-left) is valid given blocked_cell (block_r, block_c)
    # blocked_cell is None or a tuple (r, c). Returns True if the position is valid.
    def is_position_valid(i, j, blocked_cell=None):
        # Check if the 3x3 block is within the grid
        if i < 0 or j < 0 or i + 2 >= H or j + 2 >= W:
            return False
        # Check each cell in the 3x3 block
        for dx in range(3):
            for dy in range(3):
                r = i + dx
                c = j + dy
                if grid[r][c] == '#':
                    return False
                if blocked_cell is not None and (r == blocked_cell[0] and c == blocked_cell[1]):
                    return False
        return True

    # BFS to check if there's a path from start to end, given a blocked cell (optional)
    def has_path(blocked_cell=None):
        visited = [[False for _ in range(W-2)] for _ in range(H-2)]  # positions are (H-2)*(W-2) possible
        q = deque()
        start_i, start_j = start
        if not is_position_valid(start_i, start_j, blocked_cell):
            return False
        visited[start_i][start_j] = True
        q.append((start_i, start_j))
        end_i, end_j = end
        while q:
            i, j = q.popleft()
            if (i, j) == (end_i, end_j):
                return True
            # Generate all possible moves
            for di in [-1, 0, 1]:
                for dj in [-1, 0, 1]:
                    if di == 0 and dj == 0:
                        continue
                    ni = i + di
                    nj = j + dj
                    if 0 <= ni < (H-2) and 0 <= nj < (W-2):
                        if not visited[ni][nj] and is_position_valid(ni, nj, blocked_cell):
                            visited[ni][nj] = True
                            q.append((ni, nj))
        return False

    # Check original grid
    original_has_path = has_path()
    if not original_has_path:
        print(0)
        return

    # Check all allowed cells
    for (r, c) in allowed_cells:
        if not has_path((r, c)):
            print(1)
            return

    # Otherwise, output 2 (assumption)
    print(2)

if __name__ == '__main__':
    main()
0