結果

問題 No.2412 YOU Grow Bigger!
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:12:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,121 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 64,076 KB
最終ジャッジ日時 2025-03-20 21:14:33
合計ジャッジ時間 8,628 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = [list(sys.stdin.readline().strip()) for _ in range(H)]
    start = (0, 0)
    end = (H-3, W-3)  # target region's top-left corner is (H-3, W-3)

    # Directions for possible moves (8 directions)
    directions = [ (1, 0), (1, 1), (0, 1), (-1, 1),
                   (-1, 0), (-1, -1), (0, -1), (1, -1) ]

    def bfs(g):
        visited = set()
        q = deque([start])
        visited.add(start)
        while q:
            x, y = q.popleft()
            if (x, y) == end:
                return True
            for dx, dy in directions:
                nx = x + dx
                ny = y + dy
                # Check if new region is within bounds
                if 0 <= nx and nx + 2 < H and 0 <= ny and ny + 2 < W:
                    # Check all 3x3 cells in the new region
                    valid = True
                    for i in range(3):
                        for j in range(3):
                            if g[nx + i][ny + j] == '#':
                                valid = False
                                break
                        if not valid:
                            break
                    if valid and (nx, ny) not in visited:
                        visited.add((nx, ny))
                        q.append((nx, ny))
        return False

    # Check if already unreachable
    if not bfs(grid):
        print(0)
        return

    # Check each possible cell
    for i in range(H):
        for j in range(W):
            # Skip cells in the initial or target region
            if (i < 3 and j < 3) or (i >= H - 3 and j >= W - 3):
                continue
            if grid[i][j] == '.':
                # Create a copy and place a spike
                new_grid = [row.copy() for row in grid]
                new_grid[i][j] = '#'
                if not bfs(new_grid):
                    print(1)
                    return
    # If no single cell works, assume answer is higher; but this part is incomplete
    print(2)

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