Finally ACed by changing to a direct approch.
But I still don't understand what's wrong with my previous algo(which results to WA5)
It's something like this:

For example, for such a input:
4  6
1  1  2  3  3  7
4  5  2  6  6  7
4  5  8  9  12  11
10 10 8  9  12  11

1.Construct a n*m graph G, every vertices connected with all it's neighbors(up, down, left, right)
(for layout reasons here I use hex to number the vertices)

(the graph left is only a illustration to explain the things happening to the former graph.
the graph right shows the result we get in every stage.)
1-1-2-3-3-7        o-o-o-o-o-o
| | | | | |        | | | | | |
4-5-2-6-6-7        o-o-o-o-o-o
| | | | | |        | | | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| | | | | |        | | | | | |
A-A-8-9-C-B        o-o-o-o-o-o

2.Remove an edge whose endpoints have the same number.
Repeat this operation until no such pairs connected.
finally we get something like this
1 1-2-3 3-7        o o-o-o o-o
| |   | |          | |   | |
4-5-2-6 6-7        o-o-o-o o-o
    | | | |            | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| |                | |
A A-8-9-C-B        o o-o-o-o-o

3.Pick a vertex v, which has a minimum degree(non-zero), and w, an arbitrary neighbor of v.
Assign a incremental number to both v and w, and remove all the edges who cover v or w.
Repeat this operation until Δ(G) == 0.
For the input the process will be:

            (STEP1)
1 1-2-3 3-7        1 o-o-o o-o
| |   | |            |   | |
4-5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| |                | |
A A-8-9-C-B        o o-o-o-o-o

            (STEP2)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |              |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4-5-8-9-C-B        o-o-o-o-o-o
| |                | |
A A-8-9-C-B        o o-o-o-o-o

            (STEP3)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |              |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5-8-9-C-B        3 o-o-o-o-o
  |                  |
A A-8-9-C-B        3 o-o-o-o-o

            (STEP4)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |              |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5-8-9-C-B        3 o-o-o-o-o
  |                  |
A A-8-9 C B        3 o-o-o 4 4

            (STEP5)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |            | |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5-8-9-C-B        3 o-o-o-o-o
  |                  |
A A 8 9 C B        3 o 5 5 4 4

            (STEP6)
1 1-2-3 3 7        1 o-o-o 2 2
  |   |            | |   |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP7)
1 1 2 3 3 7        1 7 7 o 2 2
      |                  |
4 5-2-6 6-7        1 o-o-o o-o
    | | | |            | | | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP8)
1 1 2 3 3 7        1 7 7 o 2 2
      |                  |
4 5 2 6 6-7        1 8 8 o o-o
      | | |              | | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP9)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6-7        1 8 8 9 o-o
        | |                | |
4 5 8-9-C-B        3 6 o-o-o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP10)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6-7        1 8 8 9 o-o
        | |                | |
4 5 8 9 C-B        3 6 A A o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP11)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6 7        1 8 8 9 B B

4 5 8 9 C-B        3 6 A A o-o

A A 8 9 C B        3 6 5 5 4 4

            (STEP12)
1 1 2 3 3 7        1 7 7 9 2 2

4 5 2 6 6 7        1 8 8 9 B B

4 5 8 9 C B        3 6 A A C C

A A 8 9 C B        3 6 5 5 4 4

4.Finally we got a valid output:
1 7 7 9 2 2
1 8 8 9 B B
3 6 A A C C
3 6 5 5 4 4

I know I must mistaked something, but I can't find the mistake.
Please tell me where is wrong, or give me some tests to beat this algo.
Thanks in advance.

Edited by author 31.05.2009 00:28

I'm sorry the layout turned out to be totally unreadable.
Please copy the text to the notepad for viewing the graph edges.

It was a very good question. What's wrong with the algo?

"3. Pick a vertex v, which has a minimum degree (non-zero)..."

If there are several (not one) such vertices, we must do a choice.
Let choose the vertix (with a minimum degree) that is placed in the least row. If the row has several vertices with a minimum degree, let choose the vertix that is placed in the least column.

The next choice is the choice of w (see the algo). Let choose right neighbor of v if v is connected with it. Otherwise let choose bottom neighbor of v as w.

So we have input data that breaks the algo:

6 6
1 1 2 2 3 4
5 5 6 7 3 4
8 9 6 7 10 11
8 9 12 12 10 11
13 14 15 15 16 17
13 14 18 18 16 17

STEP 12
1   9   9   3   2   2

1   10  10  3   11  11

4   4   o - o   12  12
        |   |
o - o - o   o - o - o
|   |           |   |
o - o   6   8   o - o

5   5   6   8   7   7

STEP 13 (it is not good)
1   9   9   3   2   2

1   10  10  3   11  11

4   4   13  13  12  12

o - o - o   o - o - o
|   |           |   |
o - o   6   8   o - o

5   5   6   8   7   7


I'm sure we can build input data that makes the algo invalid if we would choose the v and w in other way.

Edited by author 23.10.2017 22:15