Art critics worldwide have only recently begun to recognize the creative genius behind the great bovine painter, Picowso.
Picowso paints in a very particular way. She starts with an N×N blank canvas, represented by an N×N grid of zeros, where a zero indicates an empty cell of the canvas. She then draws 9 rectangles on the canvas, one in each of 9 colors (conveniently numbered 1…9). For example, she might start by painting a rectangle in color 2, giving this intermediate canvas:
2220
2220
2220
0000
She might then paint a rectangle in color 7:
2220
2777
2777
0000
And then she might paint a small rectangle in color 3:
2230
2737
2777
0000
Each rectangle has sides parallel to the edges of the canvas, and a rectangle could be as large as the entire canvas or as small as a single cell. Each color from 1…9 is used exactly once, although later colors might completely cover up some of the earlier colors.
Given the final state of the canvas, please count how many of the colors still visible on the canvas could have possibly been the first to be painted.
小TY突然想画画,他有独特的艺术风格,他从N×N空白画布开始,其中0表示画布的空单元格。然后他会在画布上绘制恰好矩形,每个颜色是1到N×N中的一个。他每次可以选择任意一种未使用过的颜色进行绘画。例如,他可以从颜色2的矩形开始,画出这样的画布:
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
然后他可以用颜色7绘制一个矩形:
2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0
然后他可以在颜色3上绘制一个小矩形:
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
每个矩形都平行于画布边缘,而且矩形可以与整个画布一样大或者像一个单元一样小。每个颜色从1到正好使用一次,后来的颜色可能完全覆盖一些较早画上的颜色。
现在已知画布的最终状态,请计算有多少种颜色可能被第一个被画。