Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math.h>
- #include <string>
- using namespace std;
- struct tree
- {
- int x1, x2, y1,y2;
- tree* son[2][2];
- int value;
- };
- tree* root;
- int wymiar;
- void divide(tree* node)
- {
- for(int i=0; i<4; i++)
- {
- node->son[i%2][i/2] = new tree;
- node->son[i%2][i/2]->value = node->value;
- node->son[i%2][i/2]->x1 = node->x1+ i%2 *( node->x2-node->x1)/2;
- node->son[i%2][i/2]->y1 = node->y1 +i/2*( node->y2-node->y1)/2;
- node->son[i%2][i/2]->x2 = node->son[i%2][i/2]->x1 + ( node->x2-node->x1)/2;
- node->son[i%2][i/2]->y2 = node->son[i%2][i/2]->y1 + ( node->y2-node->y1)/2;;
- for(int a=0; a<4; a++)
- node->son[i%2][i/2]->son[a%2][a/2] = NULL;
- }
- return;
- }
- tree* find(int x1, int y1, tree* node)
- {
- if(node->x1 == x1 && node->y1 == y1 && node->y2 == y1+1 && node->x2 == x1+1)
- return node;
- else
- {
- if(node->son[0][0] == NULL)
- divide(node);
- if(node->son[0][0]->x2 <= x1)
- {
- if(node->son[0][0]->y2 <= y1)
- node = find(x1, y1, node->son[1][1]);
- else
- node = find(x1, y1, node->son[1][0]);
- }
- else
- {
- if(node->son[0][0]->y2 <= y1)
- node = find(x1, y1, node->son[0][1]);
- else
- node = find(x1, y1, node->son[0][0]);
- }
- }
- return node;
- }
- void PrintNode(tree* node, int n)
- {
- for(int i=0; i<n; i++)
- cout << " ";
- cout << "(" << node->x1 << "," << node->x2 << ") ";
- cout << "(" << node->y1 << "," << node->y2 << ")";
- if(node->son[0][0] == NULL)
- cout << node->value<< endl;
- else
- {
- cout << endl;
- n++;
- PrintNode(node->son[0][0],n);
- PrintNode(node->son[0][1],n);
- PrintNode(node->son[1][0],n);
- PrintNode(node->son[1][1],n);
- }
- }
- void merge (tree * node)
- {
- if(node->son[0][0] == NULL)
- return;
- else
- {
- for(int a=0; a<4; a++)
- merge(node->son[a%2][a/2]);
- 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)
- {
- node->value = node->son[0][0]->value;
- for(int i=0; i<4; i++)
- {
- delete(node->son[i%2][i/2]);
- node->son[i%2][i/2] = NULL;
- }
- }
- }
- }
- int main()
- {
- cout << "2^? ";
- cin >> wymiar;
- int x,y;
- string cmd;
- bool end = false;
- int value;
- root = new tree;
- tree * node = new tree;
- root->x1 = 0;
- root->y1 = 0;
- root->x2 = pow((double)2, wymiar);
- root->y2 = pow((double)2, wymiar);
- cout << "podaj wartosc poczatkowa: ";
- cin >> value;
- root->value = value;
- for(int i=0; i<4; i++)
- root->son[i/2][i%2] = NULL;
- while(!end)
- {
- cin >> cmd;
- if(cmd == "set")
- {
- cin >> x;
- cin >> y;
- cin >> value;
- node = find(x,y, root);
- cout << endl<<value<<endl;
- node->value = value;
- merge(root);
- }
- if(cmd == "print")
- PrintNode(root,0);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment