现在的位置: 首页 > 综合 > 正文

HDU 2360 (综合题)

2012年06月07日 ⁄ 综合 ⁄ 共 3924字 ⁄ 字号 评论关闭

题目意思 是任何只有一个字母不同的单词可以进行改变 最后要转换成全部不同的单词 根据理论每次转换的最小步长应该为单词长度

 

题目要求输出最小字典序的序列~~~

 

只要对输入的单词进行排序就能保证 然后首先建2张图 一张是只改变一个字母能变换的路径图 一个是都不相同单词之间的图

 

很好 下面就是BFS 使用一个数组保存父亲节点 找到后输出就可以了~~~

 

注意下BFS如果采用逐层遍历的话 使用阀值降低规模

 

以下是代码:

 

 

#include <iostream>
#include 
<queue>
#include 
<string>
using namespace std;

typedef struct  
{
    
char key[30];
}Info;

inline int cmp(const void *p1, const void *p2)
{
    Info 
*= (Info *)p1;
    Info 
*= (Info *)p2;
    
return strcmp(a->key,b->key);
}

long n,l;
long now[110];
long path[110];
bool One[110][110];
bool Map[110][110];
Info Data[
110];
long tp[110];

inline long check (Info a,Info b)
{
    
long i,j,res; 
    memset(tp,
0,sizeof(tp));
    res
=0
    
for(i=0;i<l;++i) 
    { 
        
for(j=0;j<l;++j) 
        {
            
if(!tp[j]&&a.key[i]==b.key[j]) 
            {
                
++res;
                tp[j]
=1;
                
break;
            } 
        }
    } 
    
return l-res;
}

typedef struct  
{
    
long now;
    
long pre;
    
long step;
}Node;

queue<Node> q,save;
long hash[110];

inline void BFS()
{
    
long i,j,len;
    
long cost=INT_MAX;
    
long pos=-1;

    for (i=0;i<n;++i)
    {
        
while (!q.empty())
        {
            q.pop();
        }

        for (j=0;j<n;++j)
        {
            now[j]
=j;
            hash[j]
=INT_MAX;
        }

        Node Start;
        Start.now=i;
        Start.step
=0;
        Start.pre
=i;
        q.push(Start);

        len=0;

        while (!q.empty()&&++len<=cost)
        {
            
while (!save.empty())
            {
                save.pop();
            }

            while (!q.empty())
            {
                Node t
=q.front();
                q.pop();

                if (t.step>=hash[t.now])
                {
                    
continue;
                }

                hash[t.now]=t.step;
                now[t.now]
=t.pre;
                
                
if (Map[i][t.now])
                {
                    
if (t.step<cost)
                    {
                        cost
=t.step;
                        memcpy(path,now,
sizeof(path));
                        pos
=t.now;
                        
if (cost==l)
                        {
                            
goto l1;
                        }
                    }
                    
break;
                }

                for (j=0;j<n;++j)
                {
                    
if (One[t.now][j]&&t.step+1<hash[j])
                    {
                        Node n;
                        n.pre
=t.now;
                        n.now
=j;
                        n.step
=t.step+1;
                        save.push(n);
                    }
                }

            }

            while (!save.empty())
            {
                q.push(save.front());
                save.pop();
            }
        }

    }

l1:
        //题目保证有解
        string res;
        
bool begin=true;

        while (pos!=path[pos])
        {
            
if (begin)
            {
                res
=string(Data[pos].key);
                begin
=false;
            }
            
else
            {
                res
=string(Data[pos].key)+string(" ")+res;
            }
            pos
=path[pos];
        }

        if (begin)
        {
            res
=string(Data[pos].key);
        }
        
else
        {
            res
=string(Data[pos].key)+string(" ")+res;
        }
        puts(res.data());
        res.erase();
}

int main()
{
    
long T;
    scanf(
"%ld",&T);

    while (T--)
    {
        
long i,j;
        scanf(
"%ld %ld",&n,&l);
        getchar();

        for (i=0;i<n;++i)
        {
            gets(Data[i].key);
        }

        qsort(Data,n,sizeof(Info),cmp);
        memset(One,
0,sizeof(One));
        memset(Map,
0,sizeof(Map));

        for (i=0;i<n;++i)
        {
            
for (j=i+1;j<n;++j)
            {
                
long num=check(Data[i],Data[j]);
                
if(num==1)
                {
                    One[i][j]
=One[j][i]=true;
                }
                
if (num==l)
                {
                    Map[i][j]
=Map[j][i]=true;
                }
            }
        }

        BFS();

    }

    return 0;
}

抱歉!评论已关闭.