Назад к лучшим решениям Status: AC, problem ZSUD, contest ZEL07. By levlam (Levin Aleksey), 2007-02-26 16:01:55.
  1. #include <stdio.h>
  2. #include <memory.h>
  3. #define ONLINE_JUDGE
  4. #define update(i, j)\
  5. if (a[i][j]=='.')\
  6. {\
  7. t=can[i][j][pp]++;\
  8. if (!t) B[i][j]++;\
  9. if (B[i][j]==8 && !b[i][j])\
  10. {\
  11. q[qf++]=(i<<4)+j;\
  12. b[i][j]=1;\
  13. if (qf>=100) qf-=100;\
  14. }\
  15. else if (B[i][j]==9) err=1;\
  16. }
  17.  
  18. int a[9][9];
  19. char b[9][9], eh[9][9], ev[9][9], ec[3][3][9];
  20. int B[9][9], k, can[9][9][9];
  21. int added[100], q[105], qe, qf;
  22. int D[9]={3,3,3,6,6,6,9,9,9};
  23. int DD[9]={0,0,0,1,1,1,2,2,2};
  24.  
  25. int rand(void);
  26.  
  27. #ifndef ONLINE_JUDGE
  28. void debugoutput(int z)
  29. {
  30. int i, j;
  31. printf("%d %d:\n", z, k);
  32. for (i=0; i<9; i++)
  33. {
  34. for (j=0; j<9; j++)
  35. printf("%c", a[i][j]);
  36. printf("\n");
  37. }
  38. printf("\n");
  39. }
  40. #endif
  41.  
  42. void undo(void);
  43. void obr(void);
  44.  
  45. void addcell(int x, int y, int z, int p)
  46. {
  47. int i, j, k1=D[x], k2=D[y], t, pp=p-'1', l, d, tt;
  48. char *dd=ec[DD[x]][DD[y]];
  49. int err=0;
  50. a[x][y]=p;
  51. eh[x][pp]=1;
  52. ev[y][pp]=1;
  53. dd[pp]=1;
  54. for (i=0; i<9; i++)
  55. {
  56. update(x,i);
  57. update(i,y);
  58. }
  59. for (i=k1-3; i<k1; i++)
  60. for (j=k2-3; j<k2; j++)
  61. update(i,j);
  62.  
  63. added[k++]=(x<<4)+y+(z<<8);
  64. #ifndef ONLINE_JUDGE
  65. debugoutput(z);
  66. #endif
  67.  
  68. if (err) undo();
  69. else
  70. {
  71. while (qe!=qf) obr();
  72.  
  73. for (i=k1-3; i<k1; i++)
  74. if (!eh[i][pp])
  75. {
  76. for (l=j=0; j<9 && l<2; j++)
  77. if (a[i][j]=='.' && !can[i][j][pp]) l++, t=j;
  78. if (l==0) undo();
  79. else if (l==1 && !b[i][t])
  80. addcell(i, t, 1, p);
  81. }
  82.  
  83. for (i=k2-3; i<k2; i++)
  84. if (!ev[i][pp])
  85. {
  86. for (l=j=0; j<9 && l<2; j++)
  87. if (a[j][i]=='.' && !can[j][i][pp]) l++, t=j;
  88. if (l==0) undo();
  89. else if (l==1 && !b[t][i])
  90. addcell(t, i, 1, p);
  91. }
  92.  
  93. for (d=0; d<9; d++)
  94. if (!dd[d])
  95. {
  96. l=0;
  97. for (i=k1-3; i<k1 && l<2; i++)
  98. for (j=k2-3; j<k2 && l<2; j++)
  99. {
  100. if (a[i][j]=='.' && !can[i][j][d]) l++, t=i, tt=j;
  101. if (a[i][j]==d+'1') l=2;
  102. }
  103. if (l==0) undo();
  104. else if (l==1 && !b[t][tt])
  105. addcell(t, tt, 1, d+'1');
  106. }
  107. /* for (ii=3; ii<=9; ii+=3)
  108. for (jj=3; jj<=9; jj+=3)
  109. if ((ii==k1 && jj!=k2) || (ii!=k1 && jj==k2))
  110. {
  111. l=0;
  112. for (i=ii-3; i<ii && l<2; i++)
  113. for (j=jj-3; j<jj && l<2; j++)
  114. {
  115. if (a[i][j]=='.' && !can[i][j][pp]) l++, t=i, tt=j;
  116. if (a[i][j]==p) l=2;
  117. }
  118. if (l==0) undo();
  119. else if (l==1 && !b[t][tt])
  120. addcell(t, tt, 1, p);
  121. }*/
  122. }
  123. }
  124.  
  125. int deletecell(int *x, int *y, int *p)
  126. {
  127. int z, i, j, k1, k2, t, pp;
  128. *x=added[--k];
  129. z=(*x)>>8;
  130. *y=(*x)&15;
  131. *x=(*x>>4)&15;
  132. (*p)=a[*x][*y];
  133. pp=(*p)-'1';
  134. k1=D[*x], k2=D[*y];
  135. eh[*x][pp]=0;
  136. ev[*y][pp]=0;
  137. ec[DD[*x]][DD[*y]][pp]=0;
  138. for (i=0; i<9; i++)
  139. {
  140. if (a[*x][i]=='.')
  141. {
  142. t=--can[*x][i][pp];
  143. if (!t) B[*x][i]--;
  144. }
  145. if (a[i][*y]=='.')
  146. {
  147. t=--can[i][*y][pp];
  148. if (!t) B[i][*y]--;
  149. }
  150. }
  151. for (i=k1-3; i<k1; i++)
  152. for (j=k2-3; j<k2; j++)
  153. if (a[i][j]=='.')
  154. {
  155. t=--can[i][j][pp];
  156. if (!t) B[i][j]--;
  157. }
  158. a[*x][*y]='.';
  159.  
  160. #ifndef ONLINE_JUDGE
  161. debugoutput(1000+z);
  162. #endif
  163. return z;
  164. }
  165.  
  166. void undo(void)
  167. {
  168. int x, y, p, i, *t;
  169. while (deletecell(&x, &y, &p)) ;
  170. t=can[x][y];
  171. for (i=p+1-'1'; i<9 && t[i]; i++) ;
  172. if (i>=9) undo();
  173. else addcell(x, y, 0, i+'1');
  174. }
  175.  
  176. void obr(void)
  177. {
  178. int i, x, y, *t;
  179. x=q[qe++];
  180. if (qe>=100) qe-=100;
  181. y=x&15;
  182. x>>=4;
  183. b[x][y]=0;
  184. if (B[x][y]==8)
  185. {
  186. t=can[x][y];
  187. for (i=0; i<9 && t[i]; i++) ;
  188. addcell(x, y, 1, i+'1');
  189. }
  190. }
  191.  
  192. void solve(int x, int y)
  193. {
  194. int i, *t=can[x][y];
  195. for (i=0; i<9 && t[i]; i++) ;
  196. addcell(x, y, 0, i+'1');
  197. }
  198.  
  199. int main(void)
  200. {
  201. int i, j, l, mi, mj, tn, nt;
  202. // freopen("input.txt", "r", stdin);
  203. // freopen("output.txt", "w", stdout);
  204. scanf("%d\n", &nt);
  205. for (tn=0; tn<nt; tn++)
  206. {
  207. k=0;
  208. // memset(a, '.', sizeof(a));
  209. for (i=0; i<9; i++)
  210. for (j=0; j<9; j++)
  211. a[i][j]='.';
  212. memset(B, 0, sizeof(B));
  213. memset(can, 0, sizeof(can));
  214. memset(eh, 0, sizeof(eh));
  215. memset(ev, 0, sizeof(ev));
  216. memset(ec, 0, sizeof(ec));
  217. for (i=0; i<9; i++)
  218. for (j=0; j<9; j++)
  219. {
  220. l=getchar();
  221. if (l!='.' && a[i][j]=='.') addcell(i, j, 1, l);
  222. }
  223. scanf("\n");
  224.  
  225. while (k<81)
  226. {
  227. mi=mj=0;
  228. for (i=0; i<9; i++)
  229. for (j=0; j<9; j++)
  230. if (a[i][j]=='.' && (B[i][j]>B[mi][mj] || a[mi][mj]!='.'))
  231. mi=i, mj=j;
  232. solve(mi,mj);
  233. }
  234. if (k==81)
  235. {
  236. printf("Y\n");
  237. for (i=0; i<9; i++)
  238. for (j=0; j<9; j++)
  239. printf("%c", a[i][j]);
  240. printf("\n");
  241. }
  242. else
  243. printf("N\n");
  244. }
  245. return 0;
  246. }