โจทย์ · อัลกอริทึม ปานกลาง 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 การทดสอบชุดข้อมูลขนาดใหญ่ ภายใต้เวลาจำกัด โดยไม่แสดงข้อมูลนำเข้า โจทย์ที่ส่งให้โมเดลเป็นภาษาอังกฤษ
อันดับ #1OpenAI GPT-6.1 Solแก้ผ่าน · ผ่าน 11 จาก 11 การทดสอบตอบใน 14 วินาที · เวลาประมวลผล 703 มิลลิวินาที · $0.0074 ✓ maze_steps(['..', '..'])ค่าที่คาดหวัง 2 <1 มิลลิวินาที ✓ maze_steps(['.#', '#.'])ค่าที่คาดหวัง -1 2 มิลลิวินาที ✓ maze_steps(['...#', '##.#', '....', '.##.'])ค่าที่คาดหวัง 6 <1 มิลลิวินาที ✓ 3 มิลลิวินาที✓ 3 มิลลิวินาที✓ 4 มิลลิวินาที✓ 3 มิลลิวินาที✓ 2 มิลลิวินาที✓ 6 มิลลิวินาที⏱ 288 มิลลิวินาที⏱ 390 มิลลิวินาทีโค้ด
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อันดับ #1Google Gemini 4 Argonแก้ผ่าน · ผ่าน 11 จาก 11 การทดสอบตอบใน 17 วินาที · เวลาประมวลผล 721 มิลลิวินาที · $0.0052 ✓ maze_steps(['..', '..'])ค่าที่คาดหวัง 2 3 มิลลิวินาที ✓ maze_steps(['.#', '#.'])ค่าที่คาดหวัง -1 3 มิลลิวินาที ✓ maze_steps(['...#', '##.#', '....', '.##.'])ค่าที่คาดหวัง 6 1 มิลลิวินาที ✓ 2 มิลลิวินาที✓ 1 มิลลิวินาที✓ 2 มิลลิวินาที✓ 3 มิลลิวินาที✓ 3 มิลลิวินาที✓ 4 มิลลิวินาที⏱ 286 มิลลิวินาที⏱ 413 มิลลิวินาทีโค้ด
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อันดับ #3Anthropic Claude Haiku 5.5แก้ผ่าน · ผ่าน 11 จาก 11 การทดสอบตอบใน 2.4 วินาที · เวลาประมวลผล 1.6 วินาที · $0.0003 ✓ maze_steps(['..', '..'])ค่าที่คาดหวัง 2 1 มิลลิวินาที ✓ maze_steps(['.#', '#.'])ค่าที่คาดหวัง -1 3 มิลลิวินาที ✓ maze_steps(['...#', '##.#', '....', '.##.'])ค่าที่คาดหวัง 6 3 มิลลิวินาที ✓ 3 มิลลิวินาที✓ 2 มิลลิวินาที✓ 1 มิลลิวินาที✓ 3 มิลลิวินาที✓ 1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 691 มิลลิวินาที⏱ 900 มิลลิวินาทีโค้ด
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อันดับ #4SpaceXAI Grok 4.7แก้ไม่ผ่าน · ผ่าน 0 จาก 11 การทดสอบตอบใน 120 วินาที ไม่มีโค้ดในคำตอบ
✗ maze_steps(['..', '..'])ค่าที่คาดหวัง 2ไม่มีโค้ดในคำตอบ — ✗ maze_steps(['.#', '#.'])ค่าที่คาดหวัง -1ไม่มีโค้ดในคำตอบ — ✗ maze_steps(['...#', '##.#', '....', '.##.'])ค่าที่คาดหวัง 6ไม่มีโค้ดในคำตอบ — ✗ ไม่มีโค้ดในคำตอบ✗ ไม่มีโค้ดในคำตอบ✗ ไม่มีโค้ดในคำตอบ✗ ไม่มีโค้ดในคำตอบ✗ ไม่มีโค้ดในคำตอบ✗ ไม่มีโค้ดในคำตอบ⏱ ไม่มีโค้ดในคำตอบ⏱ ไม่มีโค้ดในคำตอบ
ค่าใช้จ่ายโทเค็น: $0.01 · วิธีจัดการแข่งขันและการคิดคะแนน →