結果

問題 No.3063 Circle Balancing
ユーザー qwewe
提出日時 2025-05-14 12:57:43
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,091 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 67,720 KB
最終ジャッジ日時 2025-05-14 12:59:17
合計ジャッジ時間 3,747 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import collections
import sys

def solve():
    # Read input using sys.stdin.readline for potentially faster I/O
    r, c = map(int, sys.stdin.readline().split())
    sy, sx = map(int, sys.stdin.readline().split())
    gy, gx = map(int, sys.stdin.readline().split())

    # Adjust coordinates to be 0-based for list indexing
    start_y, start_x = sy - 1, sx - 1
    goal_y, goal_x = gy - 1, gx - 1

    # Read the maze grid
    maze = [sys.stdin.readline().strip() for _ in range(r)]

    # Initialize distance grid. -1 means unvisited.
    # Using a list of lists for the distance grid.
    dist = [[-1] * c for _ in range(r)]

    # Initialize a deque (double-ended queue) for BFS
    # Store coordinates as tuples (y, x)
    queue = collections.deque()

    # Start BFS from the starting point
    # Set distance to start as 0 and add it to the queue
    dist[start_y][start_x] = 0
    queue.append((start_y, start_x))

    # Define possible moves (up, down, left, right)
    # dy corresponds to changes in row index (y)
    # dx corresponds to changes in column index (x)
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    # BFS main loop
    while queue:
        # Dequeue the next cell to visit
        y, x = queue.popleft()

        # If we reached the goal, we found the shortest path
        if y == goal_y and x == goal_x:
            print(dist[y][x])
            return # Exit the function after printing the result

        # Explore neighbors
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]

            # Check if the neighbor is within the grid boundaries
            if 0 <= ny < r and 0 <= nx < c:
                # Check if the neighbor is an empty cell ('.')
                # and if it hasn't been visited yet (dist == -1)
                if maze[ny][nx] == '.' and dist[ny][nx] == -1:
                    # Mark the neighbor as visited by setting its distance
                    dist[ny][nx] = dist[y][x] + 1
                    # Enqueue the neighbor
                    queue.append((ny, nx))

# Call the solve function to run the code
solve()
0