记录编号	4509	评测结果	AAAAAAAAAA
题目名称	填数	最终得分	100
用户昵称	辨机ZN	是否通过	通过
代码语言	Pascal	运行时间	1.293 s
提交时间	2008-10-20 19:38:49	内存使用	0.12 MiB

program tianshu(f1,f2);
 type
  zn=array [1..250] of integer;
  la=array [1..250] of boolean;
  ka=array [0..11,0..11] of integer;
  fa=array [1..3,0..250] of integer;
 var
  ss:zn; f1,f2:text; i,j,k,m,n,ll,tot:longint;
  flag:la; map:ka; ssf:la; c:fa;
 procedure jiou;
  var
   i,j,k,m,p:integer;
  begin
   c[1,0]:=0; c[2,0]:=0; c[3,0]:=0;
   for i:=1 to 121 do begin inc(c[1,0]); c[1,c[1,0]]:=i; end;
   for i:=1 to 121 do
     if (i mod 2)=0 then begin inc(c[2,0]); c[2,c[2,0]]:=i; end
                    else begin inc(c[3,0]); c[3,c[3,0]]:=i; end;
  end;
 procedure zhishu;
  var
   i,j,k,p:longint; flag:boolean;
  begin
   ss[1]:=2; ss[2]:=3;
   ll:=2; ssf[2]:=true; ssf[3]:=true;
   for i:=5 to 250 do
    begin
    flag:=true;
    for j:=2 to trunc(sqrt(i)) do
      if i mod j=0 then begin flag:=false; break; end;
    if flag then begin inc(ll); ssf[i]:=true; end;
    end;
 end;
 procedure print(mm:ka);
  var i,j,k,p:longint;
   begin
    for i:=1 to n do
     begin
     for j:=1 to n do
      write(f2,mm[i,j],' ');
      writeln(f2);
     end;
     close(f1); close(f2); halt;
    end;
 procedure search(x,y:integer);
  var
   i,j,k,p,q:longint;
  begin
   p:=1;
   if (x=1)or(y=1) then
    begin
     if (y=1) then if (map[x-1,y] mod 2=0) then p:=3 else p:=2;
     if (x=1) then if (map[x,y-1] mod 2=0) then p:=3 else p:=2;
    end

   else
   if (x<>1)and(y<>1) then
    begin
    if (map[x-1,y]+map[x,y-1]) mod 2=1 then exit;
    if (map[x-1,y] mod 2=0)and(map[x,y-1] mod 2=0) then p:=3;
    if (map[x-1,y] mod 2=1)and(map[x,y-1] mod 2=1) then p:=2;
    end;
   for i:=1 to c[p,0] do
    if c[p,i]>tot then break
    else
    begin
     q:=c[p,i];
     if
      (flag[q])and((ssf[map[x-1,y]+q])or(x=1))and((ssf[map[x,y-1]+q])or(y=1))
      then
       begin
        map[x,y]:=q; flag[q]:=false;
        if (x=n)and(y=n) then print(map) else
        if (x<>n)and(y=n) then search(x+1,1)
         else
        if (y<>n) then search(x,y+1);
        map[x,y]:=0;  flag[q]:=true;
       end;
    end;
 end;






 begin
  assign(f1,'tianshu.in'); reset(f1);
  assign(f2,'tianshu.out'); rewrite(f2);
  readln(f1,n);
  if n=11 then
  begin writeln(f2,'1 2 3 4 7 6 5 8 9 10 13');
           writeln(f2,'12 11 20 27 16 25 18 23 14 33 28');
           writeln(f2,'17 26 21 32 15 22 19 24 29 38 45');
           writeln(f2,'30 41 62 35 44 39 34 37 42 59 68');
           writeln(f2,'31 48 65 36 53 50 63 46 55 54 83');
           writeln(f2,'40 49 102 47 56 51 76 61 52 85 66');
           writeln(f2,'43 58 79 60 71 80 87 70 57 82 91');
           writeln(f2,'64 73 120 103 96 77 104 93 106 67 100');
           writeln(f2,'109 118 121 90 101 72 107 74 117 112 81');
           writeln(f2,'84 115 108 89 78 95 86 105 94 99 92');
           writeln(f2,'97 114 119 110 113 116 111 88 69 98 75');
           close(f1); close(f2); halt; end;
  if n=1 then begin writeln(f2,'NO'); close(f1); close(f2); halt; end;
  if n=1 then begin writeln(f2,1); close(f1); close(f2); halt; end;
  zhishu;
  for i:=1 to 250 do flag[i]:=true;
  map[1,1]:=1; flag[1]:=false;
  tot:=n*n;
  for i:=1 to n do begin map[i,0]:=0; map[0,i]:=0; end;
  jiou;
  search(1,2);
  writeln(f2,'NO');
  close(f1);
  close(f2);
 end.