Назад к лучшим решениям Status: AC, problem ZSUD, contest ZEL07. By tourist (Gennady Korotkevitch), 2007-02-27 16:50:11.
  1. {$R-,S-,Q-,I-,O+}
  2. const maxn = 9;
  3. type list = array [1..maxn,1..maxn] of word;
  4. listyes = array [1..maxn,1..maxn*3] of boolean;
  5. listchar = array [1..maxn,1..maxn] of char;
  6. var
  7. kol,i,j,qq,tt: longint;
  8. ch: char;
  9. found: boolean;
  10. a: listchar;
  11. raj1,raj2,raj: array [1..maxn,1..maxn] of longint;
  12. yes: listyes;
  13. kraj,kv,last,kc,lst: array [1..maxn] of longint;
  14.  
  15. procedure rec(kol:longint);
  16. var
  17. min,ki,kj,kp,r,p,e,i,j: longint;
  18. tmpa: listchar;
  19. tmpyes: listyes;
  20. procedure updyes(i,j:longint);
  21. var c: longint;
  22. begin
  23. c:=Ord(a[i,j])-48;
  24. yes[c,i]:=True;
  25. yes[c,9+j]:=True;
  26. yes[c,18+raj[i,j]]:=True;
  27. dec(kol);
  28. end;
  29. begin
  30. if found then exit;
  31. for r:=1 to 9 do
  32. begin
  33. fillchar(kv,sizeof(kv),0);
  34. fillchar(last,sizeof(last),0);
  35. fillchar(kc,sizeof(kc),0);
  36. fillchar(lst,sizeof(lst),0);
  37. for j:=1 to 9 do
  38. if a[raj1[r,j],raj2[r,j]] = '.' then
  39. begin
  40. for p:=1 to 9 do
  41. if not (yes[p,raj1[r,j]] or yes[p,9+raj2[r,j]] or yes[p,18+r]) then
  42. begin
  43. inc(kv[p]);
  44. last[p]:=j;
  45. inc(kc[j]);
  46. lst[j]:=p;
  47. end;
  48. end
  49. else kv[Ord(a[raj1[r,j],raj2[r,j]])-48]:=-100;
  50. for i:=1 to 9 do
  51. if kv[i] = 0 then exit else
  52. if kv[i] = 1 then
  53. begin
  54. a[raj1[r,last[i]],raj2[r,last[i]]]:=Chr(i+48);
  55. updyes(raj1[r,last[i]],raj2[r,last[i]]);
  56. kv[i]:=-100;
  57. kc[last[i]]:=0;
  58. end;
  59. for i:=1 to 9 do
  60. if (a[raj1[r,i],raj2[r,i]] = '.') and (kc[i] = 0) then exit else
  61. if kc[i] = 1 then
  62. begin
  63. a[raj1[r,i],raj2[r,i]]:=Chr(lst[i]+48);
  64. updyes(raj1[r,i],raj2[r,i]);
  65. kc[i]:=0;
  66. kv[lst[i]]:=-100;
  67. end;
  68. end;
  69. for e:=1 to 9 do
  70. begin
  71. fillchar(kv,sizeof(kv),0);
  72. fillchar(kc,sizeof(kc),0);
  73. for j:=1 to 9 do
  74. if a[e,j] = '.' then
  75. begin
  76. for p:=1 to 9 do
  77. if not (yes[p,e] or yes[p,9+j] or yes[p,18+raj[e,j]]) then
  78. begin
  79. inc(kv[p]);
  80. last[p]:=j;
  81. inc(kc[j]);
  82. lst[j]:=p;
  83. end;
  84. end
  85. else kv[Ord(a[e,j])-48]:=-100;
  86. for i:=1 to 9 do
  87. if kv[i] = 0 then exit else
  88. if kv[i] = 1 then
  89. begin
  90. a[e,last[i]]:=Chr(i+48);
  91. updyes(e,last[i]);
  92. kv[i]:=-100;
  93. kc[last[i]]:=0;
  94. end;
  95. for i:=1 to 9 do
  96. if (a[e,i] = '.') and (kc[i] = 0) then exit else
  97. if kc[i] = 1 then
  98. begin
  99. a[e,i]:=Chr(lst[i]+48);
  100. updyes(e,i);
  101. kc[i]:=0;
  102. kv[lst[i]]:=-100;
  103. end;
  104. end;
  105. for e:=1 to 9 do
  106. begin
  107. fillchar(kv,sizeof(kv),0);
  108. fillchar(kc,sizeof(kc),0);
  109. for j:=1 to 9 do
  110. if a[j,e] = '.' then
  111. begin
  112. for p:=1 to 9 do
  113. if not (yes[p,j] or yes[p,9+e] or yes[p,18+raj[j,e]]) then
  114. begin
  115. inc(kv[p]);
  116. last[p]:=j;
  117. inc(kc[j]);
  118. lst[j]:=p;
  119. end;
  120. end
  121. else kv[Ord(a[j,e])-48]:=-100;
  122. for i:=1 to 9 do
  123. if kv[i] = 0 then exit else
  124. if kv[i] = 1 then
  125. begin
  126. a[last[i],e]:=Chr(i+48);
  127. updyes(last[i],e);
  128. kv[i]:=-100;
  129. kc[last[i]]:=0;
  130. end;
  131. for i:=1 to 9 do
  132. if (a[i,e] = '.') and (kc[i] = 0) then exit else
  133. if kc[i] = 1 then
  134. begin
  135. a[i,e]:=Chr(lst[i]+48);
  136. updyes(i,e);
  137. kc[i]:=0;
  138. kv[lst[i]]:=-100;
  139. end;
  140. end;
  141. // writeln((Now-td)*86400:0:3);
  142. if kol = 0 then
  143. begin
  144. writeln('Y');
  145. for i:=1 to 9 do
  146. for j:=1 to 9 do write(a[i,j]);
  147. writeln;
  148. found:=True;
  149. exit;
  150. end;
  151. min:=maxlongint;
  152. ki:=0; kj:=0;
  153. for i:=1 to 9 do
  154. for j:=1 to 9 do
  155. if a[i,j] = '.' then
  156. begin
  157. kp:=0;
  158. for e:=1 to 9 do
  159. if not (yes[e,i] or yes[e,9+j] or yes[e,18+raj[i,j]]) then inc(kp);
  160. if kp < min then
  161. begin
  162. min:=kp;
  163. ki:=i;
  164. kj:=j;
  165. end;
  166. end;
  167. i:=ki; j:=kj;
  168. tmpa:=a;
  169. tmpyes:=yes;
  170. for e:=1 to 9 do
  171. if not (yes[e,i] or yes[e,9+j] or yes[e,18+raj[i,j]]) then
  172. begin
  173. a[i,j]:=Chr(e+48);
  174. yes[e,i]:=True;
  175. yes[e,9+j]:=True;
  176. yes[e,18+raj[i,j]]:=True;
  177. rec(kol-1);
  178. yes:=tmpyes;
  179. a:=tmpa;
  180. end;
  181. a[i,j]:='.';
  182. end;
  183.  
  184. begin
  185. read(tt);
  186. for qq:=1 to tt do
  187. begin
  188. for i:=1 to 9 do
  189. for j:=1 to 9 do
  190. begin
  191. read(ch);
  192. while not (ch in ['1'..'9','.']) do read(ch);
  193. a[i,j]:=ch;
  194. end;
  195. fillchar(yes,sizeof(yes),False);
  196. kol:=0;
  197. fillchar(kraj,sizeof(kraj),0);
  198. for i:=1 to 9 do
  199. for j:=1 to 9 do
  200. begin
  201. raj[i,j]:=((i-1) div 3)*3+(j-1) div 3+1;
  202. inc(kraj[raj[i,j]]);
  203. raj1[raj[i,j],kraj[raj[i,j]]]:=i;
  204. raj2[raj[i,j],kraj[raj[i,j]]]:=j;
  205. if a[i,j] <> '.' then
  206. begin
  207. yes[Ord(a[i,j])-48,i]:=True;
  208. yes[Ord(a[i,j])-48,9+j]:=True;
  209. yes[Ord(a[i,j])-48,18+raj[i,j]]:=True;
  210. end
  211. else inc(kol);
  212. end;
  213. found:=False;
  214. rec(kol);
  215. end;
  216. end.