http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1450
输入:
     两个素数s和e(1000<s,e<9999)
输出:
    每次改变一位(要求生成的数也为素数且最高位非0),输出s到e的改变的最小次数。
解题思路:
      1.经典的bfs,当某一个节点的值第一次等于e的时候即为所求,且一定改变次数最小。
       2.用两个队列,队列1存解空间树的奇数层节点,队列2存解空间树的偶数层节点。
      3.两个队列循环出队列,入队列,队列1出的时候生成的节点全部入队列2,队列2出的时候生成的节点全部入队列1。当队列1或队列2空的时候步数加1。

核心代码:

        q1.push(s);
        isvis[s]=true;
        while(!q1.empty())
        {
            while(!q1.empty())
            {
                tmp=q1.front();
                q1.pop();
                if(tmp==e)
                {
                    flag=true;
                    break;
                }
                for(j=0;j<4;j++)
                {
                    dat[j]=tmp%10;
                    tmp/=10;
                }
                for(j=0;j<4;j++)
                {
                    tmp=0;
                    for(k=0;k<4;k++)
                        if(k!=j)
                            tmp+=dat[k]*pow((double)10,(double)k);
                    for(k=0;k<=9;k++)
                    {
                        tmp+=k*pow((double)10,(double)j);
                        if(v[tmp]==false&&tmp>1000&&isvis[tmp]==false)
                        {
                            q2.push(tmp);
                            isvis[tmp]=true;
                        }
                        tmp-=k*pow((double)10,(double)j);
                    }
                }
            }
            if(flag==true)
                break;
            cnt++;
            while(!q2.empty())
            {
                tmp=q2.front();
                q2.pop();
                q1.push(tmp);
            }
             
        }

发表评论

电子邮件地址不会被公开。

Post Navigation