시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 117 31 20 25.974%

문제

학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.

연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 $4$방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.

민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.

연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.

연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.

물건 종류 물건 모양 바람의 이동 방향
물건 1
물건 2
 
물건 3
물건 4

연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.

민상이가 원하는 자리는 몇 개 있는지 계산해주자.

입력

첫 번째 줄에는 연구실의 크기가 세로 $N(1 \le N \le 2,000)$, 가로 $M(1 \le M \le 2,000)$ 순으로 주어진다.

두 번째 줄부터 $N + 1$ 줄까지 연구실 내부 구조 정보를 알려주는 값 $M$개가 주어진다.

$1,2,3,4$는 위에서 설명한 물건의 종류이다.

$9$는 에어컨을 의미하고, $0$은 빈 공간을 의미한다.

에어컨은 $0$개 이상 $50$개 이하가 들어온다.

출력

민상이가 원하는 자리의 개수를 출력한다.

예제 입력 1

8 8
0 0 0 0 0 0 0 0
0 0 0 3 0 0 0 4
0 1 0 0 3 0 0 3
0 0 0 0 0 0 1 0
0 1 0 9 0 0 4 0
0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0

예제 출력 1

25

맨 왼쪽 맨 위를 $(1, 1)$이라 했을때 에어컨이 있는 위치는 $(5, 4)$에 있다. 

이 에어컨에서 나오는 바람의 이동과 민상이가 앉을 수 있는 자리를 표시한 그림이다.

예제 입력 2

5 5
3 0 0 0 4
0 9 2 0 0
0 1 9 1 0
0 0 2 9 0
4 0 0 0 3

예제 출력 2

17

예제 입력 3

3 3
3 0 4
0 9 0
4 0 3

예제 출력 3

5

예제 입력 4

3 5
9 0 0 0 4
4 0 0 0 0
0 0 0 0 3

예제 출력 4

15

예제 입력 5

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

예제 출력 5

0

출처