Informatica Online Judge

  병주 머신 [1936 / 0790]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 4   Total Tried : 4


The Champion of this Problem (C++) : gs15098 - 25ms / 753byte
My Best Submission (C++) : N/A

[koistudy.net (33th 전병주)]
Writer ID : [gs15098]

Background

운빨현질망겜 메이플을 즐겨하는 혁중이는 최근 카지노에 빠져있다.

특히 병주머신이라 불리우는 카지노 게임을 좋아한다.

병주머신은 다이아몬드 꼴로 세워져 있는 n*n 정사각형 모양으로, 맨 위 꼭짓점에 동전을 집어넣으면 일정한 확률로 돈 무더기가 쏟아져 나온다.

사실 병주머신의 내부 구조는 [그림 1]과 같다.


[그림 1]

돈을 넣는 투입구는 병주머신의 맨 위 꼭짓점이며, 동전은 중력에 의해 수직 방향으로 떨어진다. 중간중간마다 1*1 정사각형 꼴의 장애물(그림 1의 푸른색 마름모)이 설치되어 있으며, n*n 정사각형 모양 병주머신을 그림 1처럼 좌표계로 나타내었을 때 그 격자에 포함되어 있게 위치한다. 떨어지는 동전이 장애물을 만나면 다음 규칙에 따라 이동한다.

규칙 1. 떨어지는 동전이 사선 방향 벽면을 만나면 벽면을 따라 사선으로 이동한다. 사선 방향 벽면이 끝나면 다시 중력 방향으로 떨어진다. (그림 2)

규칙 2. 떨어지는 동전이 장애물의 꼭짓점을 만나면, 각각 50%의 확률로 그 왼쪽 사선 방향 또는 오른쪽 사선 방향으로 동전이 이동할 수 있다. (그림 3)

규칙 3. 이웃한 장애물이나 벽면 사이에는 여유 공간이 없다. 다시 말해, 붙어 있는 장애물, 벽면 사이를 통과하는 경우는 없다. (그림 4)

규칙 4. 왼쪽, 오른쪽 벽이 동시에 동전을 막은 경우, 더 이상 이동하지 않고 멈춘다. (그림 5)


[그림 2]


[그림 3]


[그림 4]


[그림 5]

병주머신에는 한 지점에 센서(그림 1, 붉은 점)가 부착되어 있다. 센서의 위치는 병주머신을 그림 1처럼 좌표계로 나타내었을 때 그 격자점 위에 위치한다.

혁중이가 돈을 받을 수 있는 조건은, 동전이 센서가 위치하는 지점을 지나갈 때이다.

아무리 돈을 걸어도 잃기만 하던 혁중이는, 사람들 몰래 병주머신을 분해하여 내부를 확인해보기로 했다.

그 결과 병주머신은 내기를 성공한 확률이 0인 구조를 가지고 있음을 확인했다.

화가 난 혁중이는 1*1 장애물을 추가로 설치하여 성공할 확률이 존재하는 병주머신을 만들기로 결심했다.

이 때, 혁중이가 필요한 1*1 장애물 부품의 최솟값을 구하시오.

Input

병주머신의 크기를 나타내는 정수 n(<=2000)이 입력된다.

그 다음 2 ~ n+1번째 줄에는 혁중이가 수정하기 전 병주머신의 1*1 타일의 배치 상태가 입력된다. 타일이 없는 상태는 0, 타일이 있는 상태는 1이다.


(단, 1행 1열에 해당하는 값은 항상 0이다.)

n+2번째 줄에는 센서의 위치 (x,y)가 입력된다. 좌표계는 다음 그림 7과 같이 정의된다.


[그림 7]

Output

필요한 1*1 장애물 부품의 최솟값을 출력한다.
단, 어떠한 방법이든 센서가 작동할 수 없을 경우 -1을 출력한다.

IO Example

입력
4
0 1 0 0
0 1 0 0
0 0 0 0
0 0 0 0
3 3

출력
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]