poj1635 - Subway tree systems

69 阅读 0 评论 46 点赞

我是靠谱客的博主健壮黑猫，最近开发中收集的这篇文章主要介绍poj1635 - Subway tree systems，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意:给出两串含有‘1’和‘0’的字符串，0表示向下搜索，1表示回溯，这样深搜一颗树
深搜完之后问这两棵树是不是同一棵树，因为树的结点顺序不同，所以可以导致树深搜的序列也不同

解题思路：其实画下样例答案显然易见，因为如果树是相同的，那么每个结点的子节点个数必然相同，
子节点可以看做成是某个结点可以深搜到的结点
我们只需要将所有的结点的子节点个数，然后【排序】之后比较每个结点的个数是否相同。因为排序之后
就是按子节点大小排序了，这样比较就是一个确定的顺序了
然后我们分析下字符串，树的结点数=‘0’的个数+根节点，我们计算子节点数可以将字符串里面的都求出来，
如果哪个下标是1，就将子节点数赋值为0即可，其实不影响什么

关于计算每个结点的子节点数，可以定义一个父亲数组，然后对每个结点都往根节点搜索，那么父亲结点的
子节点就+1，这样循环一边全部的结点就可以得出答案

因为字符串不超过3000，所有用short int即可
如果每个结点的个数相同输出same否则输出different

/*
Memory 188K
Time   16MS
*/
#include <iostream>
#include <string.h>
using namespace std;
#define MAXV 3010

short int cnt[MAXV],cnt1[MAXV];			//计算字符串下标对应的子节点个数
char str[2][MAXV];						//输入的字符串
short int pr[MAXV];						//记录每个下标的父亲结点是哪个，‘1’和根结点就是-1
short int len[2];						//定义字符串长度

int cmp(const void *a,const void *b){
	return *(short int *)b-*(short int *)a;
}

void Getparent(int x){
	int i,node=0;
	memset(pr,-1,sizeof(pr));
	for(i=1;i<len[x];i++){
		if(str[x][i]=='0'){			//为‘0’就代表node是i的父亲结点，然后把i赋给node
			pr[i]=node;
			node=i;
		}
		else node=pr[node];			//为‘1‘就node回溯到其父亲数组
	}
}

void Getcnt(int x){
	short int i,tmp;
	
	for(i=0;i<len[x];i++){			//对每个结点搜索
		tmp=i;
		while(tmp!=-1){			//不断寻找其父亲结点，让其父亲结点的子节点数+1
			tmp=pr[tmp];
			if(tmp!=-1)
				if(!x) cnt[tmp]++;
				else cnt1[tmp]++;
		}
	}
}

int main(){
	int i,Case;
	scanf("%d",&Case);
	while(Case--){
		scanf("%s%s",str[0],str[1]);
		len[0]=strlen(str[0]);
		len[1]=strlen(str[1]);
		if(len[0]!=len[1]){printf("differentn");continue;}

		memset(cnt,0,sizeof(cnt));
		memset(cnt1,0,sizeof(cnt1));
		
		Getparent(0);				//得到字符串1的所有结点的父亲数组
		Getcnt(0);					//计算字符串1的结点的子节点数

		Getparent(1);				//得到字符串2的所有结点的父亲数组
		Getcnt(1);					//计算字符串2的结点的子节点数
		
		qsort(cnt,len[0],sizeof(cnt[0]),cmp);				//对两串字符串排序
		qsort(cnt1,len[1],sizeof(cnt1[0]),cmp);
		for(i=0;i<len[0];i++){							//比较各个结点子节点数，看是不是依次对应
			if(cnt[i]!=cnt1[i]) break;
		}
			
		if(i==len[0]) printf("samen");
		else printf("differentn");
	}
	return 0;
}