Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Paint Me Less
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 994Accepted: 197Special Judge


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.

Sample Input

2 2
3 1
1 1

Sample Output

1 2 3
2 2 0


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator