首页 > 搜索 > DFS搜索 > hdu 1954 Subway tree systems-DFS-[解题报告]C++
2013
12-26

hdu 1954 Subway tree systems-DFS-[解题报告]C++

Subway tree systems

问题描述 :

Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique central station. Imagine you are a tourist in one of these cities and you want to explore all of the subway
system. You start at the central station and pick a subway line at random and jump aboard the subway car. Every time you arrive at a station, you pick one of the subway lines you have not yet travelled on. If there is none left to explore at your current station, you take the subway line back on which you first came to the station, until you eventually have travelled along all of the lines twice, once for each direction. At that point you are back at the central station. Afterwards, all you remember of the order of your exploration is whether you went further away from the central station or back towards it at any given time, i.e. you could encode your tour as a binary string, where 0 encodes taking a subway line getting you one station further away from the central station, and 1 encodes getting you one station closer to the central station.

Figure 1. To the left: A subway tree system. The larger dot is the central station. To the right: Three out of several possible encodings of exploration tours for the subway system.

输入:

On the first line of input is a single positive integer n, telling the number of test scenarios to follow.
Each test scenario consists of two lines, each containing a string of the characters ’0′ and ’1′ of length at most 3000, both describing a correct exploration tour of a subway tree system.

输出:

On the first line of input is a single positive integer n, telling the number of test scenarios to follow.
Each test scenario consists of two lines, each containing a string of the characters ’0′ and ’1′ of length at most 3000, both describing a correct exploration tour of a subway tree system.

样例输入:

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

样例输出:

same
different

用CodeBlock写题,一个VS党深受折磨,文本编辑器一般般,编译错误的提示死活看不懂

好吧,毕竟是开源的

此题题意:

给出两串含有‘1’和‘0’的字符串,0表示向下搜索,1表示回溯,这样深搜一颗树

深搜完之后问这两棵树是不是同一棵树,因为树的结点顺序不同,所以可以导致树深搜的序列也不同


用最小表示法表示一颗子树

比如样例中的

0010011101001011

有3子树

00100111 01
001011

对子树00100111,有2子树01 0011,对子树0011,有1子树01

(01)(001011)(00100111)

对于所有的子树以最小表示法表示,字典序排序,判断最后的字符串是否相同

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool cmp(string a,string b)
{
    return a.compare(b)>0;
}
string dfs(string t)
{
    string tmp;
    vector<string>m;//所有的子串
    int i=0;
    int l=0;
    int counter0=0;
    int counter1=0;
    for(;i<t.size();i++)
    {
        if(t[i]=='0')
        {
            counter0++;
        }
        else
        {
            counter1++;
        }
        if(counter0==counter1)
        {
			if(counter0==1)
			{
				tmp=t.substr(l,i-l+1);
			}
			else
			{
            tmp=t.substr(l+1,i-l);
            tmp=dfs(tmp);
            tmp=t[l]+tmp+t[i];
			}
			m.push_back(tmp);
            l=i+1;
        }
    }
    sort(m.begin(),m.end(),cmp);
    tmp.clear();
    for(i=0;i<m.size();i++)
    {
        tmp+=m[i];
    }
    return tmp;
}
int main()
{
    int total;
	cin>>total;
    while(total--)
    {
        string a,b;
        cin>>a>>b;
        a=dfs(a);
        b=dfs(b);
        if(a==b)
        {
            cout<<"same"<<endl;
        }
        else
        {
            cout<<"different"<<endl;
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/zhangwei1120112119/article/details/8689403


,
  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥