Consider a square table of size 2N+1 by 2N+1 with a cells each containing the sign “+” or the sign “−”. We call an arbitrary set of 2N+1 cells a transversal if each line and each column of the table contain exactly one cell belonging to the set.
By one operation you are allowed to change signs to opposite in all cells of one transversal. You are asked to determine if it is possible to obtain a table containing not more than 2N cells with the sign “+” by a sequence of such operations.
Input
The first line of the input contains a positive integer N not exceeding 20. The next 2N+1 lines contain the table. They consist of the symbols “+” and “-” without spaces between them.
Output
The first line of the output should contain the words “No solution” if a necessary sequence of operations does not exist. Otherwise, the first line of the output should contain the words “There is solution:” and the next lines should contain a sequence of operations that leads to the required result. Each of these lines should describe one transversal and should contain the numbers from 1 to 2N+1. Number K at position S means that the transversal includes the cell at the intersection of the line number S with the column number K. The numbers should be separated with a space.
It is sufficient to give only one sequence of operations if there exist many.
Sample
input
1
+++
++-
+-+
output
There is solution:
1 2 3
2 3 1
1 3 2
3 1 2
pascal代码:

const 
  maxn=41; 
var 
  map:array[1..maxn,1..maxn]of boolean; 
  n,i,j,x:byte; 
  c:char; 
  o:boolean; 
procedure switch(x1,x2,y1,y2:byte); 
  var 
    i:byte; 
  begin 
    map[x1,y1]:=not map[x1,y1]; 
    map[x1,y2]:=not map[x1,y2]; 
    map[x2,y1]:=not map[x2,y1]; 
    map[x2,y2]:=not map[x2,y2]; 
    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; 
begin 
  read(n);n:=n*2+1; 
  for i:=1 to n do begin 
    readln; 
    for j:=1 to n do begin 
      read(c); 
      map[i,j]:=c='+'; 
      o:=o xor map[i,j]; 
    end; 
  end; 

  writeln('There is solution:'); 
  if o then begin 
    for i:=1 to n-1 do begin 
      write(i,' '); 
      map[i,i]:=not map[i,i]; 
    end; 
    writeln(n);map[n,n]:=not map[n,n]; 
  end; 

  for i:=n downto 3 do begin 
    x:=0; 
    for j:=1 to i-1 do 
      if map[i,j] then 
        if x=0 then 
          x:=j 
        else begin 
          switch(1,i,x,j); 
          x:=0; 
        end; 
    if x>0 then begin switch(1,i,x,i);x:=0;end; 
    for j:=1 to i-1 do 
      if map[j,i] then 
        if x=0 then 
          x:=j 
        else begin 
          switch(x,j,1,i); 
          x:=0; 
        end; 
    if (x>0) and map[i,i] then switch(x,i,1,i); 
  end; 
  if ord(map[1,1])+ord(map[1,2])+ord(map[2,1])+ord(map[2,2])>2 then switch(1,2,1,2); 
end. 
0
Posted in ACM

Leave a Comment:

电子邮件地址不会被公开。