폭포수줄기

실내 폭포의 구조를 나타내는 2차원 matrix와 폭포의 시작점을 나타내는 양의 정수가 제공됩니다. 좀더 구체적으로, 폭포의 시작점은 실내 폭포의 구조물 바로 위에서 시작되어 아래로 떨어지게 됩니다.

matrix의 각 행에는 0과 1로 되어 있으며, 여기서 0은 여유 공간을 나타내고 1은 물이 통과할 수 없는 블록을 나타냅니다. matrix의 마지막 행에는 물이 결국 유입되는 양동이가 있다고 상상할 수 있습니다. 따라서 matrix의 마지막 행에는 항상 0만 포함됩니다. 또한 구조물의 양쪽에 벽이 있다는 것을 상상할 수 있는데, 이는 물이 구조물 밖으로 나갈 수 없음을 의미합니다. 물은 구조물의 벽에 갇히거나, 마지막 행의 양동이로 흐르게 됩니다.

폭포수가 아래로 흐르면서 블록에 부딪히면 해당 블록의 왼쪽과 오른쪽으로 균등하게 분할되어 흐릅니다. 즉, 폭포수의 50%가 왼쪽으로 흐르고 50%는 오른쪽으로 흐릅니다. 폭포수가 왼쪽이나 오른쪽으로 흐를 수 없는 경우(블록이나 벽 으로 인해) 해당 폭포수는 구조물안에 갇히고 더 이상 그 방향으로 계속 흐를 수 없으며, 이전 폭포수 흐름의 50%는 손실된 것을 의미합니다.

마지막으로 입력 matrix에는 최소 두 개의 행과 하나의 열이 포함되며 폭포의 시작점(배열의 첫 번째 행) 바로 아래 공간은 항상 비어 있어 폭포수가 아래로 흐를 수 있도록 합니다.

몇 퍼센트의 폭포수가 전체 구조를 통해 흐른 후 하단 양동이에 담기게 될 지를 계산하는 함수를 작성하세요.

예제 1

입력

matrix = [
  [0, 0, 0, 0, 0, 0, 0],
  [1, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 1, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 1, 0],
  [0, 0, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0],
]
source = 3

출력

[0, 0, 0, 25, 25, 0, 0]

// 폭포수는 다음과 같이 흐를 것 입니다:
// [
//   [0, 0, 0, ., 0, 0, 0],
//   [1, ., ., ., ., ., 0],
//   [0, ., 1, 1, 1, ., 0],
//   [., ., ., ., ., ., .],
//   [1, 1, 1, ., ., 1, 0],
//   [0, 0, 0, ., ., 0, 1],
//   [0, 0, 0, ., ., 0, 0]
// ]