You can always fill 2 * m area

My program got WA1 with answer
1 2 3 4
1 2 3 4
on example test
Why?

Check all 2x2 squares
A[i][j]   A[i][j+1]
A[i+1][j] A[i+1][j+1]

Make sure you always can cover this square at least one of the methods
x x
y y

or

x y
x y

Edited by author 10.12.2019 14:13

Edited by author 10.12.2019 14:15

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 passed 5 test, when change method is_inside:
from return (0<=i&&i<=n&&0<=j&&j<=m)
to return (0<=i&&i<n&&0<=j&&j<m)
what test failed me?

Could someone publish such testcase with the answer = -1?

Could someone provide me with a testcase that returns -1? paul.martynov@gmail.com

How to construct bipartite graph there?

This problem is very simple.
I think it can be more interesting if one of dimensions can be odd.

For example:
4 5
1 1 2 2 3
4 5 5 6 3
4 7 7 6 10
8 8 9 9 10

Just 122 submissions. He-he...
10 10
 1  1  3  5  7  9 11 11 13 13
15 15  3  5  7  9 17 17 19 21
23 25 25 27 29 29 31 33 19 21
23 35 37 27 39 39 31 33 41 41
49 35 37 43 43 45 45 47 47 50
49 36 38 44 44 46 46 48 48 50
24 36 38 28 40 40 32 34 42 42
24 26 26 28 30 30 32 34 20 22
16 16  4  6  8 10 18 18 20 22
 2  2  4  6  8 10 12 12 14 14

please explain me what is meaning of this problem?
I think I don't understood problem statement well and I have WA 1 :(

Help Please

before output I check arrays:

    for(i = 0; i < n; i++)
        for(j = 1; j < m; j++)
            if( a[i][j-1] == a[i][j] && b[i][j-1] == b[i][j] )
                while(1);

    for(i = 1; i < n; i++)
        for(j = 0; j < m; j++)
            if( a[i-1][j] == a[i][j] && b[i-1][j] == b[i][j] )
                while(1);

and I have wa4, not TL

Please, give me some tests to check my programm...
I have WA

bipartite perfect matching

1 2 3 4
1 2 3 4

And what sentence "that no brick in it rests on a brick from the first layer" mean? That whole brick in second row cannot rest on whole brick in first row, or ...?

And what's output for this input:

4 2
1 1
2 2
3 3
4 4

var a,b:array[1..100,1..100] of char;
    ans:array[1..100,1..100] of integer;
    m,n,i,j,top:integer;

procedure init;
var aa:array[1..100,1..100] of integer;
begin
 fillchar(a,sizeof(a),' ');
 readln(n,m);
 for i:=1 to n do
  for j:=1 to m do read(aa[i,j]);
 for i:=1 to n do
  for j:=1 to m do
  if a[i,j]=' ' then
  begin
   if a[i,j+1]=a[i,j] then
   begin
    a[i,j]:='l';
    a[i,j+1]:='r';
   end else
   begin
    a[i,j]:='u';
    a[i+1,j]:='b';
   end;
  end;
 top:=0;
 fillchar(b,sizeof(b),' ');
end;

procedure print;
var i,j:integer;
begin
 for i:=1 to n do
 begin
  for j:=1 to m do write(ans[i,j],' ');
  writeln;
 end;
end;

function can(u,v,i:integer):boolean;
begin
 if i=1 then
 begin
  if (a[u,v]<>'l')and(v+1<=m) then can:=true
                              else can:=false;
 end else
 begin
  if (a[u,v]<>'u')and(u+1<=n) then can:=true
                              else can:=false;
 end;
end;

procedure work(u,v:integer);
var i:integer;
begin
 if (u=n+1)and(v=1) then begin print; halt; end;
 if b[u,v]=' ' then
 begin
  for i:=1 to 2 do
  if can(u,v,i) then
  begin
   inc(top);
   if i=1 then
   begin
    b[u,v]:='l';
    b[u,v+1]:='r';
    ans[u,v]:=top;
    ans[u,v+1]:=top;
   end else
   begin
    b[u,v]:='u';
    b[u+1,v]:='b';
    ans[u,v]:=top;
    ans[u+1,v]:=top;
   end;
   if v+1<=m then work(u,v+1)
             else work(u+1,1);
   if i=1 then
   begin
    b[u,v]:=' ';
    b[u,v+1]:=' ';
   end else
   begin
    b[u,v]:=' ';
    b[u+1,v]:=' ';
   end;
  end;
 end else
   if v+1<=m then work(u,v+1)
             else work(u+1,1);

end;

begin
 init;
 work(1,1);
 writeln(-1);
end.