Picowso - new genius!
Picowso draws in a special way. She starts on an empty canvas of size NxN cells, represented by a grid of NxN zeros, where zero denotes an empty canvas cell. She then draws N2 rectangles on the canvas with each of the N2 colors consecutively numbered 1…N2. For example, she can start drawing a rectangle with color 2 and get a canvas like this:
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
She can then draw a rectangle with color 7:
2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0
And then she can draw a small rectangle with color 3:
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
Each rectangle has sides parallel to the sides of the canvas, and the rectangle can be as large as the entire canvas or as small as one cell. Each color from 1…N2 used exactly once, although later colors may completely overlap earlier colors.
Given the final state of the canvas, determine how many of the N2 colors could have been the first color used in the drawing.
INPUT FORMAT:
The first line of input contains NN, the size of the canvas (1≤N≤1000). The next N lines describe the final painting on the canvas, each line contains NN integers in the interval 0…N2. It is guaranteed that the picture was drawn in the manner described above, by drawing rectangles of various colors.
OUTPUT FORMAT:
Print the number of colors that could have been used first.
|
Enter |
Output |
|
4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
|
14 |
In this example, color 2 could have been used first. Color 3 was used after color 7, and color 7 was used after color 2. Since we can't see the other colors, we conclude that they could also have been used first (and then recolored).