URAL/1092

来自"NOCOW"

我解释一下maigo的程序

我们可以一个折脚，一个折脚这样的消;

所谓折脚，就是指点(i,i)即它左边的一行((i,j)其中j=1~i)和上面的一列((j,i)其中j=1~i);

就像下图

i=4

OOOAO

OOOAO

OOOAO

AAAAO

OOOOO

其中A代表折脚区域;

显然我们可以通过两次操作让一个矩形的四个顶点变换一次（请读者自行琢磨）；

这样我们让i=n*2+1 downto 1,每次把一个折脚上的加号消去，就是两两配对，消完之后，每个折脚上最多剩一个加号；

因为一共有n*2+1个折脚，所以最多有n*2+1个加号；

其中如果刚好有n*2+1个加号，则每次折脚都剩了一个加号，可以知道每次相消前折脚上都有奇数个加号，所以原图中一共有奇数个加号；

反过来，如果原图中一共有偶数个加号，那么最后一定不会形成刚好n*2+1个加号，所以我们一开始可以通过一次操作使得原图中剩下偶数个加号；

我的程序:

program djy;
var
  map:array[1..50,1..50] of boolean;
  n,m:longint;
procedure init;
var
  i,j:longint;
  x:char;
begin
  readln(n);
  n:=n*2+1;
  for i:=1 to n do
  begin
    for j:=1 to n do
    begin
      read(x);
      map[i,j]:=x='+';
      if map[i,j]=true then m:=m+1;
    end;
    readln;
  end;
end;
procedure switch(x1,y1,x2,y2:longint);   {通过两次操作使得以(x1,y1),(x2,y2)为左上角和右下角的矩形的四个顶点变换}
var
  i:longint;
begin
  map[x1,y1]:=not(map[x1,y1]);
  map[x2,y2]:=not(map[x2,y2]);
  map[x1,y2]:=not(map[x1,y2]);
  map[x2,y1]:=not(map[x2,y1]);
  for i:=1 to n do
  begin
    if i=x1 then write(y1)
    else if i=x2 then write(y2)
    else if i=y1 then write(x1)
    else if i=y2 then write(x2)
    else write(i);
    if i=n then writeln
    else write(' ');
  end;
  for i:=1 to n do
  begin
    if i=x1 then write(y2)
    else if i=x2 then write(y1)
    else if i=y1 then write(x1)
    else if i=y2 then write(x2)
    else write(i);
    if i=n then writeln
    else write(' ');
  end;
end;
procedure main;
var
  i,j,last:longint;
begin
  writeln('There is solution:');
  if m mod 2=1 then                      {如果原图中共有奇数个加号}
  begin
    for i:=1 to n do
    begin
      write(i,' ');
      map[i,i]:=not(map[i,i]);
    end;
    writeln;
  end;
  for i:=n downto 1 do
  begin
    last:=0;                         {消去行上的折脚}
    for j:=1 to i-1 do
    if map[i,j]=true then
    begin
      if last=0 then last:=j
      else
      begin
        switch(1,last,i,j);
        last:=0;
      end;
    end;
    if last<>0 then switch(1,last,i,i);
 
    last:=0;                          {消去列上的折脚}
    for j:=1 to i-1 do
    if map[j,i]=true then
    begin
      if last=0 then last:=j
      else
      begin
        switch(last,1,j,i);
        last:=0;
      end;
    end;
    if (last<>0) and (map[i,i]=true) then switch(last,1,i,i);
  end;
end;
begin
  init;
  main;
end.