結果

問題 No.2731 Two Colors
ユーザー lam6er
提出日時 2025-03-31 17:27:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,682 ms / 3,000 ms
コード長 3,136 bytes
コンパイル時間 235 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 124,108 KB
最終ジャッジ日時 2025-03-31 17:28:18
合計ジャッジ時間 22,341 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        row = list(map(int, input().split()))
        grid.append(row)
    
    # Initialize color array with -1 (uncolored), 0 for (H-1, W-1), 1 for (0,0)
    color = [[-1 for _ in range(W)] for __ in range(H)]
    color[0][0] = 1
    color[H-1][W-1] = 0
    
    # Check if initial cells are adjacent
    initial_dist = (H-1) + (W-1)
    if initial_dist == 1:
        print(0)
        return
    
    # Prepare heaps and inclusion trackers for both colors
    heap0 = []
    heap1 = []
    included0 = [[False for _ in range(W)] for __ in range(H)]
    included1 = [[False for _ in range(W)] for __ in range(H)]
    
    # Initialize heap1 with neighbors of (0,0)
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = 0 + dx, 0 + dy
        if 0 <= nx < H and 0 <= ny < W and color[nx][ny] == -1:
            heapq.heappush(heap1, (grid[nx][ny], nx, ny))
            included1[nx][ny] = True
    
    # Initialize heap0 with neighbors of (H-1, W-1)
    x, y = H-1, W-1
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and color[nx][ny] == -1:
            heapq.heappush(heap0, (grid[nx][ny], nx, ny))
            included0[nx][ny] = True
    
    step_count = 0
    while True:
        current_step = step_count + 1
        current_color = current_step % 2
        current_heap = heap1 if current_color == 1 else heap0
        other_color = 0 if current_color == 1 else 1
        
        # Find the next cell to color in current_color
        found = False
        while current_heap:
            A_val, x, y = heapq.heappop(current_heap)
            if color[x][y] != -1:
                continue  # Skip already colored cells
            # Color this cell
            color[x][y] = current_color
            found = True
            # Check neighbors for other_color
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W:
                    if color[nx][ny] == other_color:
                        print(current_step)
                        return
            # Add uncolored neighbors to the heap
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and color[nx][ny] == -1:
                    if current_color == 1:
                        if not included1[nx][ny]:
                            heapq.heappush(heap1, (grid[nx][ny], nx, ny))
                            included1[nx][ny] = True
                    else:
                        if not included0[nx][ny]:
                            heapq.heappush(heap0, (grid[nx][ny], nx, ny))
                            included0[nx][ny] = True
            break  # Processed the cell, exit the loop
        
        if not found:
            # No cells to process, should not happen as per problem constraints
            break
        step_count += 1

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