結果

問題 No.2731 Two Colors
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:57:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,227 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,136 KB
実行使用メモリ 171,980 KB
最終ジャッジ日時 2025-03-26 15:58:48
合計ジャッジ時間 16,444 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    H = int(input[idx])
    idx += 1
    W = int(input[idx])
    idx += 1
    
    A = []
    for _ in range(H):
        row = list(map(int, input[idx:idx+W]))
        idx += W
        A.append(row)
    
    # Using 0-based indices
    color = [[-1 for _ in range(W)] for _ in range(H)]
    color[0][0] = 1  # (1,1) becomes (0,0)
    color[H-1][W-1] = 0  # (H,W) becomes (H-1, W-1)
    
    heap0 = []
    heap1 = []
    
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Initialize heap1 with cells adjacent to (0,0)
    for di, dj in dirs:
        ni = 0 + di
        nj = 0 + dj
        if 0 <= ni < H and 0 <= nj < W:
            if color[ni][nj] == -1:
                heapq.heappush(heap1, (A[ni][nj], ni, nj))
    
    # Initialize heap0 with cells adjacent to (H-1, W-1)
    for di, dj in dirs:
        ni = (H-1) + di
        nj = (W-1) + dj
        if 0 <= ni < H and 0 <= nj < W:
            if color[ni][nj] == -1:
                heapq.heappush(heap0, (A[ni][nj], ni, nj))
    
    steps = 0
    while True:
        steps += 1
        current_color = steps % 2
        current_heap = heap1 if current_color == 1 else heap0
        
        # Find the next valid cell in the current heap
        while True:
            if not current_heap:
                break  # This should not happen per problem statement
            val, i, j = current_heap[0]
            if color[i][j] == -1:
                break
            heapq.heappop(current_heap)
        else:
            break  # No more cells to process
        
        # Color the cell
        val, i, j = heapq.heappop(current_heap)
        color[i][j] = current_color
        
        # Check all adjacent cells
        for di, dj in dirs:
            ni = i + di
            nj = j + dj
            if 0 <= ni < H and 0 <= nj < W:
                if color[ni][nj] == 1 - current_color:
                    print(steps)
                    return
                elif color[ni][nj] == -1:
                    heapq.heappush(current_heap, (A[ni][nj], ni, nj))
    
    print(steps)  # This line is theoretically unreachable

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