문제 설명

한 도시에 큰 사고가 발생하여 응급차가 부상자를 구조하기 위해 출동해야 합니다. 도시는 m x n크기의 이진 행렬로 표현되며, 0은 차량이 통행 가능한 도로를, 1은 통행이 불가능한 구역을 나타냅니다. 응급차는 도시의 왼쪽 위(0, 0)에서 출발하여 오른쪽 아래(m-1, n-1)에 위치한 부상자를 구조해야 합니다.

응급차는 이동 가능한 도로(0)만을 따라 상하좌우 또는 대각선으로 인접한 칸으로 이동할 수 있으며, 경로의 길이는 방문한 칸의 개수로 정의됩니다. 만약 응급차가 부상자에게 도달할 수 없는 경우, -1을 반환해야 합니다. 도로망을 분석하여 응급차가 도착할 수 있는 가장 짧은 경로의 길이를 반환하는 solution 함수를 작성해주세요.

입출력 예시

예시 1:

• 입력:

  city = [
      [0, 0, 1, 0],
      [1, 0, 1, 0],
      [1, 0, 0, 0]
  ]
  

• 출력: 4

• 설명: (0, 0) -> (1, 1) -> (2, 2) -> (2, 3)

예시 2:

• 입력:

  city = [
      [0, 1, 0],
      [0, 1, 0],
      [0, 0, 0],
      [1, 1, 0],
      [0, 0, 0]
  ]
  

• 출력: 5

• 설명: (0, 0) -> (1, 0) -> (2, 1) -> (3, 2) -> (4, 2)

예시 3:

• 입력:

  city = [
      [0, 0, 0, 0],
      [1, 1, 1, 0],
      [1, 0, 0, 0],
      [1, 1, 1, 1]
  ]
  

• 출력: -1

• 설명: 도착점 (3,3)의 값이 1이기 때문에 방문할 수 없습니다.

예시 4:

• 입력:

  city = [
      [1, 0, 0, 0],
      [1, 1, 1, 0],
      [1, 0, 0, 0],
      [1, 1, 1, 0]
  ]
  

• 출력: -1

• 설명: 시작점 (0,0)의 값이 1이기 때문에 출발할 수 없습니다.

제한 사항

• m == city.length

• n == city[i].length

• city은 m x n 크기의 2차원 리스트이며, 1 ≤ m, n ≤ 300입니다.

• city[i][j]는 0 또는 1로만 구성됩니다.