Paint Me Less
Time Limit: 10000MS
Memory Limit: 65536K
Alice likes drawing very much. But, maybe, precisely speaking, she just loves painting a sheet of paper into a single color. Today she gets a paper with some colors on it and she starts to paint it all black. The rectangular paper is divided into several rows and columns. Each block, with a single color, is connected to four other blocks which are the blocks directly upper, lower, left or right to it. All the blocks with the same color and connected to each other forms a region. Every time Alice paints, she chooses one region and paint all blocks of that region with a same color, which counted as a step. Unfortunately, Alice is not good at math. And she always paints a lot of times which makes her tired and unhappy. Could you help her painting in an easy way?
The input file contains multiple cases until the end of file. The first line of each case consists of two integers, R and C (1≤R≤4, 1≤C≤4), which stands for the number of rows and columns of the paper. There are R lines follows which describes the original paper. Each line contains C integers, which the j-th integer of the i-th line describes the color of block (i,j) (1≤i≤R, 1≤j≤C).Colors are represented by integers in the range [0, 19]. And the target color, which Alice wants to paint the whole paper into, is zero.
For each test case, print an integer S, the minimal steps Alice must paint, on the first line. Then describe your solution in the following S lines in this format:
x1 y1 c1
x2 y2 c2
xS yS cS
That means at step i Alice should paint the whole region containing block (xi,yi) into color ci.
PKU Campus 2009 (POJ Monthly Contest – 2009.0