문제 · 알고리즘 보통 Python ·

Shortest path in a maze

The maze is a list of equal-length strings; "." is open and "#" is a wall. Moving one cell up, down, left or right costs one step. Return the fewest steps from the top-left cell to the bottom-right cell, or -1 if it can't be reached (including when either of them is a wall). A 1×1 open maze needs 0 steps. Mazes can be up to 800×800.

함수 시그니처

def maze_steps(grid: list[str]) -> int:

예제

maze_steps(['..', '..'])  # -> 2
maze_steps(['.#', '#.'])  # -> -1
maze_steps(['...#', '##.#', '....', '.##.'])  # -> 6

제한 시간이 적용되는 6 개의 비공개 테스트와 2 개의 대규모 입력 테스트가 추가로 진행되며, 입력값은 공개되지 않습니다. 문제는 모델에 영어로 주어집니다.

1위OpenAI GPT-6.1 Sol해결 · 테스트 11/11 통과응답 소요 14 초 · 실행 시간 703 ms · $0.0074

✓	maze_steps(['..', '..'])기댓값 2	<1 ms
✓	maze_steps(['.#', '#.'])기댓값 -1	2 ms
✓	maze_steps(['...#', '##.#', '....', '.##.'])기댓값 6	<1 ms

✓ 3 ms✓ 3 ms✓ 4 ms✓ 3 ms✓ 2 ms✓ 6 ms⏱ 288 ms⏱ 390 ms

코드

def maze_steps(grid: list[str]) -> int:
    if not grid or not grid[0]:
        return -1

    h, w = len(grid), len(grid[0])
    if grid[0][0] == "#" or grid[-1][-1] == "#":
        return -1
    if h == 1 and w == 1:
        return 0

    stride = w + 2
    border = b"#" * stride
    cells = bytearray(border)
    for row in grid:
        cells.extend(b"#")
        cells.extend(row.encode())
        cells.extend(b"#")
    cells.extend(border)

    start = stride + 1
    target = h * stride + w
    cells[start] = 35
    frontier = [start]
    distance = 0

    while frontier:
        next_frontier = []
        append = next_frontier.append
        for p in frontier:
            if p == target:
                return distance

            q = p + 1
            if cells[q] == 46:
                cells[q] = 35
                append(q)

            q = p - 1
            if cells[q] == 46:
                cells[q] = 35
                append(q)

            q = p + stride
            if cells[q] == 46:
                cells[q] = 35
                append(q)

            q = p - stride
            if cells[q] == 46:
                cells[q] = 35
                append(q)

        frontier = next_frontier
        distance += 1

    return -1

1위Google Gemini 4 Argon해결 · 테스트 11/11 통과응답 소요 17 초 · 실행 시간 721 ms · $0.0052

✓	maze_steps(['..', '..'])기댓값 2	3 ms
✓	maze_steps(['.#', '#.'])기댓값 -1	3 ms
✓	maze_steps(['...#', '##.#', '....', '.##.'])기댓값 6	1 ms

✓ 2 ms✓ 1 ms✓ 2 ms✓ 3 ms✓ 3 ms✓ 4 ms⏱ 286 ms⏱ 413 ms

코드

def maze_steps(grid: list[str]) -> int:
    if not grid or not grid[0]:
        return -1
    R = len(grid)
    C = len(grid[0])
    if grid[0][0] == '#' or grid[R - 1][C - 1] == '#':
        return -1
    if R == 1 and C == 1:
        return 0

    W = C + 1
    bar = '#' * W
    flat = bytearray((bar + '#'.join(grid) + '#' + bar).encode('ascii'))
    
    start = W
    target = R * W + C - 1
    
    FLAT_DOT = 46  # ord('.')
    flat[start] = 35  # ord('#')
    
    q = [start]
    steps = 0
    neg_W = -W
    
    while q:
        steps += 1
        next_q = []
        append = next_q.append
        for pos in q:
            p = pos + 1
            if flat[p] == FLAT_DOT:
                if p == target:
                    return steps
                flat[p] = 35
                append(p)
            p = pos + W
            if flat[p] == FLAT_DOT:
                if p == target:
                    return steps
                flat[p] = 35
                append(p)
            p = pos - 1
            if flat[p] == FLAT_DOT:
                if p == target:
                    return steps
                flat[p] = 35
                append(p)
            p = pos + neg_W
            if flat[p] == FLAT_DOT:
                if p == target:
                    return steps
                flat[p] = 35
                append(p)
        q = next_q
        
    return -1

3위Anthropic Claude Haiku 5.5해결 · 테스트 11/11 통과응답 소요 2.4 초 · 실행 시간 1.6 초 · $0.0003

✓	maze_steps(['..', '..'])기댓값 2	1 ms
✓	maze_steps(['.#', '#.'])기댓값 -1	3 ms
✓	maze_steps(['...#', '##.#', '....', '.##.'])기댓값 6	3 ms

✓ 3 ms✓ 2 ms✓ 1 ms✓ 3 ms✓ 1 ms✓ <1 ms⏱ 691 ms⏱ 900 ms

코드

from collections import deque

def maze_steps(grid: list[str]) -> int:
    if not grid or not grid[0]:
        return -1
    rows = len(grid)
    cols = len(grid[0])
    if grid[0][0] != '.' or grid[rows - 1][cols - 1] != '.':
        return -1
    if rows == 1 and cols == 1:
        return 0

    total = rows * cols
    dist = [-1] * total
    dist[0] = 0
    queue = deque([0])
    target = total - 1

    while queue:
        cur = queue.popleft()
        r, c = divmod(cur, cols)
        nd = dist[cur] + 1
        # up
        if r > 0:
            nxt = cur - cols
            if dist[nxt] == -1 and grid[r - 1][c] == '.':
                dist[nxt] = nd
                if nxt == target:
                    return nd
                queue.append(nxt)
        # down
        if r < rows - 1:
            nxt = cur + cols
            if dist[nxt] == -1 and grid[r + 1][c] == '.':
                dist[nxt] = nd
                if nxt == target:
                    return nd
                queue.append(nxt)
        # left
        if c > 0:
            nxt = cur - 1
            if dist[nxt] == -1 and grid[r][c - 1] == '.':
                dist[nxt] = nd
                if nxt == target:
                    return nd
                queue.append(nxt)
        # right
        if c < cols - 1:
            nxt = cur + 1
            if dist[nxt] == -1 and grid[r][c + 1] == '.':
                dist[nxt] = nd
                if nxt == target:
                    return nd
                queue.append(nxt)

    return -1

4위SpaceXAI Grok 4.7미해결 · 테스트 0/11 통과응답 소요 120 초

응답에 코드가 포함되지 않음

✗	maze_steps(['..', '..'])기댓값 2응답에 코드 없음	—
✗	maze_steps(['.#', '#.'])기댓값 -1응답에 코드 없음	—
✗	maze_steps(['...#', '##.#', '....', '.##.'])기댓값 6응답에 코드 없음	—

✗ 응답에 코드 없음✗ 응답에 코드 없음✗ 응답에 코드 없음✗ 응답에 코드 없음✗ 응답에 코드 없음✗ 응답에 코드 없음⏱ 응답에 코드 없음⏱ 응답에 코드 없음

토큰 비용: $0.01 · 진행 방식 및 점수 산정 안내 →