Nidhogg

aisd plansza/drzewa

May 11th, 2012
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <math.h>
  3. #include <string>
  4. using namespace std;
  5.  
  6. struct tree
  7. {
  8.     int x1, x2, y1,y2;
  9.     tree* son[2][2];
  10.     int value;
  11. };
  12.  
  13. tree* root;
  14. int wymiar;
  15.  
  16.  
  17. void divide(tree* node)
  18. {
  19.     for(int i=0; i<4; i++)
  20.     {
  21.         node->son[i%2][i/2] = new tree;
  22.  
  23.  
  24.         node->son[i%2][i/2]->value = node->value;
  25.         node->son[i%2][i/2]->x1 = node->x1+ i%2 *( node->x2-node->x1)/2;
  26.         node->son[i%2][i/2]->y1 = node->y1 +i/2*( node->y2-node->y1)/2;
  27.         node->son[i%2][i/2]->x2 = node->son[i%2][i/2]->x1 + ( node->x2-node->x1)/2;
  28.         node->son[i%2][i/2]->y2 = node->son[i%2][i/2]->y1 + ( node->y2-node->y1)/2;;
  29.         for(int a=0; a<4; a++)
  30.             node->son[i%2][i/2]->son[a%2][a/2] = NULL;
  31.     }
  32.  
  33.     return;
  34. }
  35.  
  36.  
  37. tree* find(int x1, int y1, tree* node)
  38. {
  39.     if(node->x1 == x1 && node->y1 == y1 && node->y2 == y1+1 && node->x2 == x1+1)
  40.         return node;
  41.     else
  42.     {
  43.         if(node->son[0][0] == NULL)
  44.             divide(node);
  45.        
  46.         if(node->son[0][0]->x2 <= x1)
  47.         {
  48.             if(node->son[0][0]->y2 <= y1)
  49.                 node = find(x1, y1, node->son[1][1]);
  50.             else
  51.                 node = find(x1, y1, node->son[1][0]);
  52.         }
  53.         else
  54.         {
  55.             if(node->son[0][0]->y2 <= y1)
  56.                 node = find(x1, y1, node->son[0][1]);
  57.             else
  58.                 node = find(x1, y1, node->son[0][0]);  
  59.         }
  60.     }
  61.     return node;
  62. }
  63. void PrintNode(tree* node, int n)
  64. {
  65.  
  66.     for(int i=0; i<n; i++)
  67.         cout << " ";
  68.         cout << "(" << node->x1 << "," << node->x2 << ") ";
  69.        cout << "(" << node->y1 << "," << node->y2 << ")";
  70.        if(node->son[0][0] == NULL)
  71.            cout << node->value<< endl;
  72.        else
  73.        {
  74.        cout << endl;
  75.        n++;
  76.        PrintNode(node->son[0][0],n);
  77.        PrintNode(node->son[0][1],n);
  78.        PrintNode(node->son[1][0],n);
  79.        PrintNode(node->son[1][1],n);
  80.        }
  81. }
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97. void merge (tree * node)
  98. {
  99.     if(node->son[0][0] == NULL)
  100.         return;
  101.     else
  102.     {
  103.         for(int a=0; a<4; a++)
  104.             merge(node->son[a%2][a/2]);
  105.         if(node->son[0][0]->value == node->son[1][0]->value && node->son[0][1]->value == node->son[1][1]->value && node->son[0][0]->value == node->son[1][1]->value)
  106.         {
  107.            
  108.             node->value = node->son[0][0]->value;
  109.             for(int i=0; i<4; i++)
  110.             {
  111.                 delete(node->son[i%2][i/2]);
  112.                 node->son[i%2][i/2] = NULL;
  113.             }
  114.            
  115.            
  116.         }
  117.     }
  118.  
  119.  
  120. }
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128. int main()
  129. {
  130.     cout << "2^? ";
  131.     cin >> wymiar;
  132.     int x,y;
  133.     string cmd;
  134.     bool end = false;
  135.     int value;
  136.     root = new tree;
  137.     tree * node = new tree;
  138.     root->x1 = 0;
  139.     root->y1 = 0;
  140.     root->x2 = pow((double)2, wymiar);
  141.     root->y2 = pow((double)2, wymiar);
  142.     cout << "podaj wartosc poczatkowa: ";
  143.     cin >> value;
  144.     root->value = value;
  145.     for(int i=0; i<4; i++)
  146.         root->son[i/2][i%2] = NULL;
  147.     while(!end)
  148.     {
  149.         cin >> cmd;
  150.         if(cmd == "set")
  151.         {
  152.             cin >> x;
  153.             cin >> y;
  154.             cin >> value;
  155.             node = find(x,y, root);
  156.             cout << endl<<value<<endl;
  157.             node->value = value;
  158.             merge(root);
  159.         }
  160.         if(cmd == "print")
  161.             PrintNode(root,0);
  162.  
  163.        
  164.        
  165.     }
  166.  
  167.  
  168.  
  169.     return 0;
  170. }
Advertisement
Add Comment
Please, Sign In to add comment