32831번 - Colorful Quadrants 다국어

문제

You are given an $n \times n$ grid, and some of the grid points are colored by one of the $k$ colors. The color of a point is represented by an integer from 0ドル$ to $k,ドル where 0ドル$ represents the uncolored case. Note that multiple points may be colored the same. The rows and columns of the grid are denoted by integers from 1ドル$ to $n,ドル and a point located at row $i$ and column $j$ is denoted by $(i,j)$. For an uncolored point $(i,j)$ that satisfies 1ドル < i < n$ and 1ドル < j < n,ドル we define four sub-grids by removing row $i$ and column $j$ from the grid. Each of the four sub-grids is called NW (northwest), NE (northeast), SW (southwest), and SE (southeast) based on the position relative to $(i,j)$. We say that $(i,j)$ has colorful quadrants if, when selecting one point from each of the four sub-grids, the chosen four points are all of different colors.

See Figure C.1(a) as a 5ドル \times 5$ grid example. The point $(2,3)$ has colorful quadrants because NW has color 1ドル,ドル NE has color 4ドル,ドル SW has color 3ドル,ドル and SE has color 2ドル,ドル as shown in Figure C.1(b). However, the point $(4,3)$ does not have colorful quadrants because both SW and SE have color 2ドル$ only, as shown in Figure C.1(c).

Figure C.1

Given an $n \times n$ grid containing at least four grid points colored in different colors, write a program to count the number of uncolored points that have colorful quadrants.

입력

Your program is to read from standard input. The input starts with a line containing two integers, $n$ and $k$ (3ドル ≤ n ≤ 2,000円,ドル 4ドル ≤ k ≤ 1,000円$), where $n$ is the number of rows and columns of the grid and $k$ is the number of colors. In the following $n$ lines, the $i$-th line contains $n$ integers that represent the colors of the points $(i,j)$ for 1ドル ≤ j ≤ n$. The integer $c$ that represents the color of a point is in range 0ドル ≤ c ≤ k$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the number of uncolored points that have colorful quadrants.

제한

힌트