Assignment #6: Maze

Problem

You find yourself in a perplexing maze, a 2D grid of strings stretching out before you. Each string represents either a 1 (a wall) or a 0 (an open path). The maze is a perfect square, and all outer edges are blocked, leaving you trapped within.

You must find a path from the starting point A, located at the top edge of the maze, to the destination point B, situated at the bottom edge.

The Rules of Engagement

Movement: You can move up, down, left, or right, but never diagonally. You can only move one step at a time.

Boundaries: The outer edges of the maze are impenetrable walls.

Starting and Ending Points: Your journey begins at A on the top edge and ends at B on the bottom edge.

Your Objective: Find the shortest path from A to B and return its length.

Constraints:

• 10 <= n == height == width <= 10^3

당신은 혼란스러운 미로 속에 갇혔습니다. 이 미로는 2차원 문자열 그리드로 구성되어 있으며, 각 칸은 1(벽) 또는 0(빈 경로)을 나타냅니다. 이 미로는 정사각형 형태이며, 바깥쪽 가장자리는 모두 벽으로 막혀 있어 외부로 나갈 수 없습니다.

당신은 미로의 위쪽 경계에 위치한 시작 지점 A에서 출발하여, 아래쪽 경계에 있는 도착 지점 B에 도달해야 합니다.

• 이동: 상하좌우로만 이동할 수 있으며, 대각선으로는 이동할 수 없습니다. 한 번에 한 칸씩만 이동 가능합니다.

• 경계: 미로의 바깥쪽 테두리는 모두 벽으로 막혀 있어 통과할 수 없습니다.

• 시작/도착 지점: A에서 시작하여 B로 이동해야 합니다.

• 목표: A에서 B까지의 최단 경로를 찾아 그 경로의 길이를 반환합니다.

제약 사항:

• 10 <= n == 높이 == 너비 <= 10^3

Input specification

A maze, a 2D grid of strings.

maze: 2차원 문자열 그리드

Output specification

The length of the shortest path from A to B.

A에서 B까지의 최단 경로의 길이

Example

Sample 0

<< in
111111111A1
10000000001
10101110111
10101000001
11101011101
10001010001
10111011111
10001000101
10101010101
10101010001
111B1111111

>> out
20

Sample visualization 0 (Not a part of the output)

111111111A1
100+++++++1
101+1110111
101+1000001
111+1011101
1+++1010001
1+111011111
1+++1000101
101+1010101
101+1010001
111B1111111

[(0, 9), (1, 9), (1, 8), (1, 7), (1, 6), (1, 5), (1, 4), (1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (5, 2), (5, 1), (6, 1), (7, 1), (7, 2), (7, 3), (8, 3), (9, 3), (10, 3)]

Sample 1

<< in
111A1111111
10001000001
11101110111
10000000001
10111011101
10101010001
10101011101
10100010001
11111010101
10000010101
111111111B1

>> out
16

Sample visualization 1 (Not a part of the output)

111A1111111
100+1000001
111+1110111
100+++++++1
101110111+1
101010100+1
101010111+1
101000100+1
111110101+1
100000101+1
111111111B1

[(0, 3), (1, 3), (2, 3), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9), (9, 9), (10, 9)]

More sample data: link