UVa122 Trees on the level

2428 단어 두 갈래 나무
제목: 두 갈래 트리를 입력하고 단계별로 출력합니다.만약 트리가 완전하지 않거나 노드가 여러 번 부여된다면, notcomplete를 출력합니다.
생각: BFS.사실 이 문제를 푸는 것은 수조를 시험적으로 이용하여 동적 트리 구조를 저장하기 위해서이다.
#include <iostream>         
#include <stdio.h>         
#include <cmath>         
#include <algorithm>         
#include <iomanip>         
#include <cstdlib>         
#include <string>         
#include <memory.h>         
#include <vector>         
#include <queue>         
#include <stack>         
#include <map>       
#include <set>       
#include <ctype.h>         
#define INF 1000000010     
#define ll long long     
#define max3(a,b,c) max(a,max(b,c))     
#define MAXN 1000

using namespace std;     

char str[32];

int node[1024];
int l[1024];
int r[1024];

int last;
int cur;
bool ok;

void addnode (char* pos,int n){
	for(int i=0;;i++){
		if(pos[i]==')'){
			if(node[cur]!=-1)ok=false;
			node[cur]=n;
			//cout<<n<<" "<<cur<<endl;
			break;
		}
		if(pos[i]=='L'){
			if(l[cur]==-1){
				last++;
				l[cur]=last;
				cur=last;
			}else{
				cur=l[cur];
			}
		}
		if(pos[i]=='R'){
			if(r[cur]==-1){
				last++;
				r[cur]=last;
				cur=last;
			}else{
				cur=r[cur];
			}
		}
	}
}

int main(){
	while(cin>>str){
	
		if(strlen(str)==2)continue;
		memset(l,-1,sizeof(l));
		memset(r,-1,sizeof(r));
		memset(node,-1,sizeof(node));
		last=0;
		cur=0;
		ok=true;
		
		int k=strchr(str,',')-str;
		int t=0;
		for(int i=1;i<k;i++){
			t*=10;
			t+=str[i]-'0';
		}
		addnode(strchr(str,',')+1,t);
		
		while(true){
			cin>>str;
			if(strlen(str)==2)break;
			cur=0;
			int k=strchr(str,',')-str;
			int t=0;
			for(int i=1;i<k;i++){
				t*=10;
				t+=str[i]-'0';
			}
			addnode(strchr(str,',')+1,t);
		}
		
		vector<int> ans;
		
		queue<int> que;
		que.push(0);
		while(!que.empty()){
			int cur=que.front(); que.pop();
			ans.push_back(node[cur]);
			if(node[cur]==-1)ok=false;
			if(l[cur]!=-1){
				que.push(l[cur]);
			}
			if(r[cur]!=-1){
				que.push(r[cur]);
			}
		}
		
		if(ok){
			int siz=ans.size();
			for(int i=0;i<siz;i++){
				printf("%d",ans[i]);
				if(i!=siz-1)printf(" ");
			}
			cout<<endl;
		}else{
			cout<<"not complete"<<endl;
		}
	}
	return 0;
}

좋은 웹페이지 즐겨찾기