시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 418 128 74 28.137%

문제

CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하지 않는다. 하지만 영조의 행동이 답답한 영조의 친구 보성이는 영조가 위, 아래로만 가는 걸 막기 위해 영조와 같이 다니며 왼쪽으로 최대 L번 오른쪽으로 최대 R번만큼 이동할 수 있게 영조를 도와준다. 영조와 보성이는 지도 밖으로는 나가지 않는다.

갈수 있는 땅, 벽의 위치, 영조와 보성이의 출발 위치가 지도 정보로 주어졌을 때 영조와 보성이가 출발 위치로부터 이동해서 갈 수 있는 모든 땅의 개수를 구해보자.

다음은 이해를 돕기 위한 예제1 그림이다.

영조와 보성이가 시작 위치에서 갈수 있는 땅은 파란색, 벽이 있어 갈수 없는 땅은 검은색이다.

다음 그림은 영조와 보성이가 시작 위치에서 왼쪽으로 한 칸 이동했을 때이다.

왼쪽으로 한 칸 이동하였으므로 더 이상 왼쪽으로는 갈 수 없고, 현재 상태에서 갈수 있는 길은 파란색으로 나타내었다.

다음 그림은 영조와 보성이가 시작 위치에서 아래로 갔을 때이다.

영조와 보성이가 아래로 한 칸 이동했을 때의 갈 수 있는 땅과 현재 상태이다.

다음 그림은 영조와 보성이가 자유롭게 이동하였을 때 도달 가능한 땅을 나타낸다.

영조와 보성이가 최대 왼쪽으로 L번, 오른쪽으로 R번 만큼 움직여서 자유롭게 이동했을 때 도달 가능한 땅은 13칸이다.

입력

첫 번째 줄에 지도의 행과 열 N, M이 주어진다 (1 ≤ N, ≤ 1,000)

두 번째 줄에 왼쪽과 오른쪽으로 갈수 있는 최대 횟수 L, R이 주어진다. (0 ≤ L, RM)

세 번째 줄부터 N+2줄까지 의 크기만큼 지도가 주어진다.

  • 0: 갈 수 있는 땅
  • 1: 벽이 있어 갈 수 없는 땅
  • 2: 영조와 보성이가 있는 위치

출력

시작 위치를 포함하여 갈수 있는 땅의 개수를 출력한다.

예제 입력 1

5 5
1 1
00000
00000
02100
10000
00000

예제 출력 1

13

예제 입력 2

4 5
1 2
00000
11010
02011
10000

예제 출력 2

10