2009年4月8日星期三

继续暴力搜索,SGU 125

题目大意:有两个 NxN (N<=3) 的矩阵 A、B。1 <= A[i, j] <= 9,B[i, j] 表示 A 中与 A[i, j] 相邻的<=4个格子内比 A[i, j] 大的格子数。给出 B,求 A。

为什么叫作继续呢。。。。。我也不好多说了。。。。。结果是 23ms 的 AC,能排上第一页了,不错不错。。。


program sgu_125;
{$APPTYPE CONSOLE}
const
 NS = 'NO SOLUTION';
 
var
 N: Integer;
 i, j: Integer;
 a11, a12, a13, a21, a22, a23, a31, a32, a33: Integer;
 b11, b12, b13, b21, b22, b23, b31, b32, b33: Integer;

begin
 readln(N);
 if N = 1 then
  begin
   readln(a11);
   if a11 <> 0 then
    writeln(NS)
   else
    writeln(1)
  end
 else if N = 2 then
  begin
   readln(b11, b12);
   readln(b21, b22);
   for a11 := 1 to 9 do
    for a12 := 1 to 9 do
     for a21 := 1 to 9 do
      if ord(a21 > a11) + ord(a12 > a11) = b11 then
       for a22 := 1 to 9 do
        if ord(a11 > a12) + ord(a22 > a12) = b12 then
         if ord(a11 > a21) + ord(a22 > a21) = b21 then
          if ord(a12 > a22) + ord(a21 > a22) = b22 then
           begin
            writeln(a11, ' ', a12);
            writeln(a21, ' ', a22);
            readln;
            halt
           end;
   writeln(NS)
  end
 else
  begin
   readln(b11, b12, b13);
   readln(b21, b22, b23);
   readln(b31, b32, b33);
   for a11 := 1 to 9 do
    for a12 := 1 to 9 do
     for a21 := 1 to 9 do
      if ord(a12 > a11) + ord(a21 > a11) = b11 then
       for a22 := 1 to 9 do
        if ord(a12 > a22) + ord(a21 > a22) <= b22 then
         for a13 := 1 to 9 do
          if ord(a11 > a12) + ord(a13 > a12) + ord(a22 > a12) = b12 then
           for a31 := 1 to 9 do
            if ord(a11 > a21) + ord(a31 > a21) + ord(a22 > a21) = b21 then
             for a23 := 1 to 9 do
              if (ord(a12 > a13) + ord(a23 > a13) = b13) and
               (ord(a12 > a22) + ord(a21 > a22) + ord(a23 > a22) <= b22) then
               for a33 := 1 to 9 do
                if ord(a13 > a23) + ord(a22 > a23) + ord(a33 > a23) = b23 then
                 for a32 := 1 to 9 do
                  if (ord(a22 > a32) + ord(a33 > a32) + ord(a31 > a32) = b32) and
                   (ord(a12 > a22) + ord(a21 > a22) + ord(a23 > a22) + ord(a32 > a22) = b22) and
                   (ord(a32 > a31) + ord(a21 > a31) = b31) and
                   (ord(a32 > a33) + ord(a23 > a33) = b33) then
                   begin
                    writeln(a11, ' ', a12, ' ', a13);
                    writeln(a21, ' ', a22, ' ', a23);
                    writeln(a31, ' ', a32, ' ', a33);
                    halt
                   end;
   writeln(NS)
  end
end.