장기에서 마(말)와 체스에서 나이트는 상하좌우 한 칸 앞으로 전진한 후에 대각선 방향으로 한 칸 전진한 곳으로만 이동할 수 있다.

나이트는 마와는 달리 앞에 가로막는 기물이 있어도 뛰어넘을 수 있다. 둘 중 어느 것도 장애물 위에 놓일 수 없다.

n*n짜리 판 위에 장애물이 k개 있을 때, 체스판의 임의의 위치 (x,y)에서 시작하여 나이트와 마는 각각 체스판의 어떤 위치로 이동할 수 있다.(이동이 불가능할 수도 있다)

문제는 체스판의 각 칸에 대해 나이트가 마보다 빨리 갈 수 있는 칸의 개수를 구하는 것이다.

마는 이동할 수 없지만 나이트는 이동할 수 있는 칸에 대해서는 나이트가 빨리 갈 수 있다고 간주하고, 두 말 모두 이동할 수 없는 경우에는 세지 않는다.

원래 마는 간선의 교차점 위에 놓이지만 이 문제에서는 나이트처럼 블록 중심에 놓인다고 가정한다. 각 말은 체스판 밖으로 나갈 수 없다.

입력

• 첫 줄에는 정수 n과 k가 주어진다. n은 1000이하의 자연수이고, k는 900000이하의 자연수이다.
• 다음 n개의 줄에는 체스판의 정보가 주어진다. 각 줄에는 n개의 0 또는 1인 정수가 주어진다. 1은 장애물이 있는 위치를 나타낸다.
• 다음으로 나이트(마)가 출발하는 위치 x, y가 주어진다. x는 행, y는 열 번호이다. 각 정수는 1이상 n이하이다.

출력

입출력 예

입력

4 2
1 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0
2 3

출력

9

입출력 보충

x 2 3 4

2 3 0 3

1 2 x 2

4 1 2 1

마가 갈 수 있는 곳

x 2 5 x

6 x 0 3

1 4 x 6

x 7 2 x

출처: sharifa