v 0. Pasted by slipstak2 as cpp at 2011-04-07 19:34:52 MSK and set expiration to never.

Paste will expire never.

  1. #pragma comment (linker, "/STACK:64000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include <string.h>
  7. #include <string>
  8. #include <algorithm>
  9. #include <cmath>
  10.  
  11. using namespace std;
  12.  
  13. #define MATRIX matrixCOL
  14. const char EMPTY = '0';
  15. const int LAST_DIGITS = 4;
  16.  
  17. const int N = 9;
  18. const int REQS_AMOUNT = 4;
  19. const int BLOCK = (int)sqrt((double)N);
  20. const int ROW_MAX = N * N * N;
  21. const int COL_MAX = REQS_AMOUNT * N * N;
  22.  
  23. const int ROW_OFFSET = 0*N*N;
  24. const int COL_OFFSET = 1*N*N;
  25. const int SQU_OFFSET = 2*N*N;
  26. const int CEL_OFFSET = 3*N*N;
  27.  
  28. struct head;
  29. struct node {
  30.  
  31.     head* header;
  32.  
  33.     node* left;
  34.     node* right;
  35.     node* up;
  36.     node* down;
  37.     int data;
  38.  
  39.     int row; int col;
  40.     node()
  41.     {
  42.         left = right = up = down = 0;
  43.         data = -1;
  44.     }
  45.     node(int Data, head* Header, int Row, int Col) {
  46.         left = right = up = down = 0;
  47.         data = Data;
  48.         header = Header;
  49.         row = Row;
  50.         col = Col;
  51.     }
  52.     bool isEmpty() {
  53.         return left == 0;
  54.     }
  55. };
  56. struct head : node
  57. {
  58.     size_t size;
  59.     head(){size = 0;}
  60. };
  61.  
  62. int sud[N][N];
  63. //vector<vector<int> > sud = vector<vector<int> > (N, vector<int>(N));
  64.  
  65. int squ(int row, int col) {
  66.     return row / BLOCK * BLOCK + col / BLOCK;
  67. }
  68. inline int pack(int row, int col, int val) {
  69.     return row * N * N + col * N + val;
  70. }
  71. inline int pack(int X, int val) {
  72.     return X * N + val;
  73. }
  74. inline void unpack(int cur, int &row, int &col, int &val) {
  75.     row = cur / N / N; cur %= N*N;
  76.     col = cur / N;     cur %= N;
  77.     val = cur;
  78. }
  79.  
  80. inline void AddInCol(head* curHeader, node* curNode) {
  81.     curNode->up = curHeader->up;
  82.     curNode->down = curHeader;
  83.     curHeader->up->down = curNode;
  84.     curHeader->up = curNode;
  85.     curHeader->size++;
  86. }
  87. inline void AddInRow(node* &curRowBegin, node* curNode) {
  88.  
  89.     if (!curRowBegin) {
  90.         curRowBegin = curNode;
  91.         curRowBegin->left = curRowBegin;
  92.         curRowBegin->right = curRowBegin;
  93.     }
  94.     else {
  95.         curNode->left = curRowBegin->left;
  96.         curNode->right = curRowBegin;
  97.         curRowBegin->left->right = curNode;
  98.         curRowBegin->left = curNode;
  99.  
  100.     }
  101. }
  102. inline void AddRow(int index, int row_pos, int col_pos, int squ_pos, int cel_pos, head* Header, node* Rows[]) {
  103.  
  104.     int hpos [REQS_AMOUNT] = {row_pos,    col_pos,    squ_pos,    cel_pos};
  105.     //int dpos[REQS_AMOUNT] = {ROW_OFFSET, COL_OFFSET, SQU_OFFSET, CEL_OFFSET};
  106.     for (int j=0; j<REQS_AMOUNT; j++) {
  107.         node* newNode = new node(index, &Header[hpos[j]], index, hpos[j]);
  108.         AddInCol(&Header[hpos[j]], newNode);
  109.         AddInRow(Rows[index], newNode);
  110.     }
  111. }
  112. void initMatrix(head &root, head* Header, node* Rows[]) {
  113.     root.right = &Header[0];
  114.     Header[0].left = &root;
  115.  
  116.     root.left =  &Header[COL_MAX-1];
  117.     Header[COL_MAX-1].right = &root;
  118.  
  119.     for (int i=0;i<COL_MAX;i++) {
  120.         Header[i].up = Header[i].down = &Header[i];
  121.         if (i != COL_MAX - 1) {
  122.             Header[i].right= &Header[i+1];
  123.             Header[i+1].left = &Header[i]; // может быть это лишнее (нихера не лишнее)
  124.         }
  125.     }
  126.     int index;
  127.     for (int row = 0; row < N; row++) {
  128.         for (int col = 0; col < N; col++) {
  129.             for (int val = 0; val < N; val++) {
  130.  
  131.                 index = pack(row, col, val);
  132.                 AddRow( pack(row, col, val),
  133.                         ROW_OFFSET + pack(row,val),
  134.                         COL_OFFSET + pack(col,val),
  135.                         SQU_OFFSET + pack(squ(row,col),val),
  136.                         CEL_OFFSET + pack(row,col),
  137.                         Header, Rows);
  138.             }
  139.         }
  140.     }
  141. }
  142. void out_line(){
  143.     int size = COL_MAX + 4 * N + 5 + 5;
  144.     if (N>4) size++;
  145.     for (int k=0;k<=size;k++)
  146.         printf("-");
  147.     printf("\n");
  148. }
  149. string get_head_str(char mod, int num) {
  150.     char buf[10];
  151.     string str;
  152.     sprintf(buf,"%c=%d",mod,num);
  153.     str = string(buf);
  154.     int pos = 0;
  155.     while (str.size() < N){
  156.         if (pos&1)  str += " ";
  157.         else str = " " + str;
  158.         pos++;
  159.     }
  160.     return str;
  161. }
  162. void out_header(){
  163.     if (N>4) {
  164.         printf("__________");if (N>4) printf("_");
  165.         for (int i=0;i<=COL_MAX;i++){
  166.             if (i%N==0) printf("|");
  167.             if (i<COL_MAX) printf("%d", i/100);
  168.         }
  169.         printf("\n");
  170.     }
  171.     printf("__________"); if (N>4) printf("_");
  172.     for (int i=0;i<=COL_MAX;i++){
  173.         if (i%N==0) printf("|");
  174.         if (i<COL_MAX) printf("%d", (i/10)%10);
  175.     }
  176.     printf("\n");
  177.     printf("__________"); if (N>4) printf("_");
  178.     for (int i=0;i<=COL_MAX;i++){
  179.         if (i%N==0) printf("|");
  180.         if (i<COL_MAX) printf("%d", i%10);
  181.     }
  182.     printf("\n");
  183.     if (N<9) printf("_№_| R C V|");
  184.     else     printf("__№_| R C V|");
  185.    
  186.     for (int i=0;i<N;i++)
  187.         printf("%s|", get_head_str('R',i).c_str());
  188.     for (int i=0;i<N;i++)
  189.         printf("%s|", get_head_str('C',i).c_str());
  190.     for (int i=0;i<N;i++)
  191.         printf("%s|", get_head_str('S',i).c_str());
  192.     for (int i=0;i<N;i++) {
  193.         for (int j=0;j<N;j++)
  194.             printf("%d",(i*N + j)%10);
  195.         printf("|");
  196.     }
  197.     printf("\n");
  198. }
  199. bool isRowEmpty(int matrix[][COL_MAX], int row) {
  200.     for (int col=0;col<COL_MAX;col++)
  201.         if (matrix[row][col])
  202.             return false;
  203.     return true;
  204. }
  205. char * getLastAddressDigit(int address, int lastDigits) {
  206.  
  207.     char *buf = new char[10];
  208.     sprintf(buf,"0x%X",address);
  209.     buf += strlen(buf) - lastDigits;
  210.     for (size_t i=0;i<strlen(buf);i++)
  211.         buf[i] = tolower(buf[i]);
  212.     return buf;
  213. }
  214. void output_spaces(int a, int b){
  215.     int amount = 0;
  216.     for (int i = a+1; i<=b; i++) {
  217.         if (i%N==0 && i!=0)
  218.             amount++;
  219.     }
  220.     bool isBorder = false;
  221.     if (b % N == 0 && b <= COL_MAX && a % N != 0) {
  222.         isBorder = true;
  223.         amount--;
  224.     }
  225.     if (isBorder)
  226.         printf("|");
  227.     for (int i=0;i<amount;i++)
  228.         printf(" ");
  229.    
  230. }
  231.  
  232. bool isEqual(int mr[][COL_MAX], int mc[][COL_MAX]) {
  233.     for (int i=0;i<COL_MAX;i++) {
  234.         for (int j=0;j<ROW_MAX;j++)
  235.             if (mr[i][j] != mc[i][j])
  236.                 return false;
  237.     }
  238.     return true;
  239. }
  240. void out_matrix(int matrix[][COL_MAX]) {
  241.     for (int i=0; i<=ROW_MAX; i++) {
  242.  
  243.         int row,col,val;
  244.         unpack(i,row,col,val);
  245.         if (i%N == 0)
  246.             out_line();
  247.         if (i < ROW_MAX) {
  248.             if (N<9) printf("%0.2d | %d %d %d", i, row, col, val);
  249.             else     printf("%0.3d | %d %d %d", i, row, col, val);
  250.             if (!isRowEmpty(matrix,i)) {
  251.                 for (int j=0;j<=COL_MAX; j++) {
  252.                     if (j % N == 0)
  253.                         printf("|");
  254.                     if (j<COL_MAX) {
  255.                         if (matrix[i][j]) {
  256.                             printf("1[%s]",getLastAddressDigit(matrix[i][j],LAST_DIGITS));
  257.                             int delta = LAST_DIGITS + 2;
  258.                             j += delta;
  259.                             output_spaces(j - delta,j);
  260.                         }
  261.                         else
  262.                             printf(" ");
  263.                     }
  264.                 }
  265.             }
  266.             printf("\n");
  267.         }
  268.     }
  269. }
  270. void checkMatrix(head *Header, node* Rows[]) {
  271.     int matrixCOL[ROW_MAX][COL_MAX];
  272.     memset(matrixCOL,0,sizeof(matrixCOL));
  273.    
  274.     for (int j=0;j<COL_MAX;j++) {
  275.         if (Header[j].size !=0) {
  276.             for (node* curNode = Header[j].down; curNode != &Header[j]; curNode = curNode->down) {
  277.                 matrixCOL[curNode->data][j] = (int)curNode;
  278.             }
  279.         }
  280.     }
  281.  
  282.     /*int matrixROW[ROW_MAX][COL_MAX];
  283.     memset(matrixROW,0,sizeof(matrixROW));
  284.    
  285.     for (int i=0;i<ROW_MAX;i++) {
  286.         if (Rows[i]) {
  287.             node* curNode = Rows[i];
  288.             int pos = 0;
  289.             do
  290.             {
  291.                 matrixROW[curNode->row][curNode->col] = (int)curNode;
  292.                 curNode = curNode->right;
  293.             } while (curNode != Rows[i]);
  294.         }
  295.     }
  296.     if (isEqual(matrixROW, matrixCOL))
  297.         printf("MATRIXes ARE EQUAL\n");
  298.     else
  299.         printf("ALARM!!!\n");*/
  300.  
  301.     out_header();
  302.     out_matrix(MATRIX);
  303. }
  304.  
  305. void cover(head* header) {
  306.    
  307.     header->right->left = header->left;
  308.     header->left->right = header->right;
  309.  
  310.     for (node* curNode = header->down; curNode != header; curNode = curNode->down) {
  311.         header->size--;
  312.         for (node* rowNode = curNode->right; rowNode != curNode; rowNode = rowNode->right)
  313.         {
  314.             rowNode->up->down = rowNode->down;
  315.             rowNode->down->up = rowNode->up;
  316.             rowNode->header->size--;
  317.         }
  318.     }
  319. }
  320. void uncover(head* header) {
  321.     header->right->left = header;
  322.     header->left->right = header;
  323.  
  324.     for (node* curNode = header->down; curNode != header; curNode = curNode->down) {
  325.         header->size++;
  326.         for (node* rowNode = curNode->right; rowNode != curNode; rowNode = rowNode->right) {
  327.             rowNode->up->down = rowNode;
  328.             rowNode->down->up = rowNode;
  329.             rowNode->header->size++;
  330.         }
  331.     }
  332. }
  333. void SolutionRow(node* Node) {
  334.     node *rowNode = Node;
  335.     do{
  336.        
  337.         cover(rowNode->header);
  338.         rowNode = rowNode->right;
  339.     }
  340.     while (rowNode != Node);
  341. }
  342. void UnCoverRow(node* Node) {
  343.     node *rowNode = Node;
  344.     do{
  345.  
  346.         uncover(rowNode->header);
  347.         rowNode = rowNode->right;
  348.     }
  349.     while (rowNode != Node);
  350. }
  351. int input(head *Header, node* Rows[]) {
  352.     int solCell = 0;
  353.     memset(sud,0,sizeof(sud));
  354.     for (int i=0;i<N;++i)
  355.         for (int j=0; j<N; ++j)
  356.             sud[i][j] = 0;
  357.     char buf[N+1];
  358.     for (int i=0;i<N;i++) {
  359.         scanf("%s\n",&buf);
  360.         for (int j=0;j<N;j++){
  361.             if (buf[j] != EMPTY)
  362.             {
  363.                 sud[i][j] = buf[j] - '0';
  364.                 int index = pack(i,j,sud[i][j]-1);
  365.                 SolutionRow(Rows[index]);
  366.                 solCell++;
  367.             }               
  368.         }
  369.     }
  370.     return solCell;
  371. }
  372. void solve(head *root, int pos, bool &isFound) {
  373.     if (pos == N*N) {
  374.         // output
  375.         for (int i=0;i<N;i++) {
  376.             for (int j=0;j<N;j++)
  377.                 printf("%d", sud[i][j]);
  378.             printf("\n");
  379.         }
  380.         isFound = true;
  381.         return;
  382.     }
  383.     int row,col,val;
  384.     for (node* Node = root->right->down; Node != root->right; Node = Node->down) {
  385.         unpack(Node->data,row,col,val);
  386.        
  387.         sud[row][col] = val + 1;
  388.         SolutionRow(Node);
  389.        
  390.         solve(root,pos+1,isFound);
  391.         if (isFound) return;
  392.  
  393.         UnCoverRow(Node);
  394.         sud[row][col] = 0; // debug only       
  395.     }
  396. }
  397. void out_headers(head* Header, head* root) {
  398.     int dig = 3;
  399.     for (int i=0;i<COL_MAX;i++) {
  400.         printf("(%0.2d)%s %d; ", i, getLastAddressDigit((int)&Header[i],dig), Header[i].size);
  401.     }
  402.     printf("\n");
  403.     for (head* Node = (head*)root->right; Node != root; Node = (head*)Node->right)
  404.         printf("(  )%s %d; ", getLastAddressDigit((int)(Node),dig), Node->size);
  405.     printf("\n\n");
  406. }
  407. int main() {
  408.  
  409. #ifdef _DEBUG
  410.     freopen("input.txt","r",stdin);
  411.     freopen("output.txt","w",stdout);
  412. #endif
  413.     int tests;
  414.     scanf("%d\n", &tests);
  415.     for (int i=0;i<tests;i++) {
  416.  
  417.         head root;
  418.         head Header[COL_MAX];
  419.         node* Rows[ROW_MAX];
  420.         memset(Rows,0,sizeof(Rows));
  421.  
  422.        
  423.         initMatrix(root, Header, Rows);
  424.         //out_headers(Header,&root);
  425.         int pos = input(Header, Rows);
  426.         //out_headers(Header, &root);
  427.         //checkMatrix(Header, Rows);
  428.         bool isFound = false;
  429.         solve(&root,pos, isFound);
  430.     }
  431.  
  432.     return 0;
  433. }


Editing is locked.