这个是代码
#include <iostream>
#include <algorithm>
using namespace std;
char map[60000][60000];
struct Node{
int x,y;
int step,place;
int left=0,right=0;
}node[100000];
struct deleteL{
int step,place;
};
int m,n;
void drawSlash(int current){
if (node[current].step == m){
return;
}
//构造左杠
int nx = node[current].x+1,ny = node[current].y-1;
while(map[nx][ny] != 'o'){
map[nx][ny] = '/';
nx++;ny--;
}
nx = node[current].x+1,ny = node[current].y+1;
while(map[nx][ny] != 'o'){
map[nx][ny] = '\\';
nx++;ny++;
}
drawSlash(node[current].left);
drawSlash(node[current].right);
}
void draw(int current){
map[node[current].x][node[current].y] = 'o';
if (node[current].step == m){
return;
}
node[current].left = current*2;
node[current].right = current*2+1;
//构造左孩子和右孩子
//构造行坐标
if (node[current].place == 1){
node[node[current].left].x = node[current].x + (node[current].y+1)/2;
node[node[current].right].x = node[current].x + (node[current].y+1)/2;
node[node[current].left].y = node[current].y - (node[current].y+1)/2;
node[node[current].right].y = node[current].y + (node[current].y+1)/2;
}
else{
int i = current;
while(node[--i].place!=1);
node[node[current].left].x = node[i].x + (node[i].y+1)/2;
node[node[current].right].x = node[i].x + (node[i].y+1)/2;
node[node[current].left].y = node[current].y - (node[i].y+1)/2;
node[node[current].right].y = node[current].y + (node[i].y+1)/2;
}
//构造列坐标
node[node[current].left].step = node[current].step+1;
node[node[current].right].step = node[current].step+1;
node[node[current].left].place = node[current].place + node[current].place-1;
node[node[current].right].place = node[current].place + node[current].place;
draw(node[current].left);
draw(node[current].right);
}
/*
o
o o
o o o o
*/
void printMap(){
int nodeSum = (1<<m)-1;
int maxX = 1;
int maxY = 1;
for(int i = 1;i<=nodeSum;i++){
if (node[i].x > maxX){
maxX = node[i].x;
}
if (node[i].y > maxY){
maxY = node[i].y;
}
}
for(int i = 1;i<=maxX;i++,cout << endl){
for(int j = 1;j<=maxY;j++){
cout << map[i][j];
}
}
}
void printTree(){
for(int i = 1;i<=(1<<m)-1;i++){
cout << "node="<<i<<"x=" << node[i].x << "y=" << node[i].y << "place="<<node[i].place<<"step="<<node[i].step<< endl;
}
}
void deleteTree(int step,int place){
int current;
for(int i = 1;i<=(1<<m)-1;i++){
if (node[i].step == step && node[i].place == place){
current = i;
break;
}
}
map[node[current].x][node[current].y] = ' ';
if (step == m){
return;
}
//删除左斜杠
int nx = node[current].x+1,ny = node[current].y-1;
while(map[nx][ny] != 'o'){
map[nx][ny] = ' ';
nx++;ny--;
}
//删除右斜杠
nx = node[current].x+1,ny = node[current].y+1;
while(map[nx][ny] != 'o'){
map[nx][ny] = ' ';
nx++;ny++;
}
//删除左右子树
deleteTree(node[current].step+1,node[current].place + node[current].place-1);
deleteTree(node[current].step+1,node[current].place + node[current].place);
}
bool cmp(deleteL a,deleteL b){
return a.step < b.step;
}
int main(){
fill(map[0],map[0]+60000*60000,' ');
cin >> m >> n;
deleteL deleteList[50];
//构造根节点
int leafSum = (1<<m) - (1<<(m-1));
node[1].x = 1;
node[1].y = leafSum*3/2;
node[1].step = 1;
node[1].place = 1;
//画画
draw(1);
drawSlash(1);
for(int i = 0;i<n;i++){
cin >> deleteList[i].step >> deleteList[i].place;
}
sort(deleteList,deleteList+n,cmp);
for(int i = 0;i<n;i++){
int step = deleteList[i].step;
int place = deleteList[i].place;
//寻找节点
int j;
for(j = 1;j<=(1<<m)-1;j++){
if(node[j].step == step && node[j].place == place){
break;
}
}
//寻找头上枝条
int nx,ny;
if (map[node[j].x-1][node[j].y-1] == '\\'){
nx = node[j].x-1,ny=node[j].y-1;
while(map[nx][ny] != 'o'){
map[nx][ny] = ' ';
nx--;ny--;
}
}
else if(map[node[j].x-1][node[j].y+1] == '/'){
nx = node[j].x-1,ny=node[j].y+1;
while(map[nx][ny] != 'o'){
map[nx][ny] = ' ';
nx--;ny++;
}
}
deleteTree(step,place);
}
//打印画作
printMap();
}