洛谷 题解 P1467 【循环数 Runaround Numbers】

eh...我把这道题做成了搜索！

主要思路：从输入的数+1开始，不断往上循环，判断该数是否为循环数。

这道题主要考验你的耐心，看起来容易，做起来难！

话不多说，奉上AC代码（注释均在代码内）

#include<iostream>
using namespace std;
int x;
int cnt;
int old_num[12],num[12];
bool ans[12];
void statistics(int a)//统计该数的数位长度和各个数位
{
    cnt=0;
    while(a!=0)
    {
        cnt++;
        old_num[cnt]=a%10;
        a/=10;
    }
}
bool all()//判断每一位是否都遍历过了
{
    for(int i=1;i<=cnt;i++)
    {
        if(!ans[i])
            return false;
    }
    return true;
}
bool dfs(int pointer)
{
    int far;//指循环到的下一位
    far=(pointer+num[pointer])%cnt;
    if(far==0)
        far=cnt;
    if(far==1&&all())//全部遍历过且下一位是第一位，就是循环数
        return true;
    if(far==1&&!all())//虽然下一位是第一位但是并没有把每一位全部遍历，还不是循环数
        return false;
    if(ans[far]==true)//如果下一位不是第一位但是下一位已经遍历过，不是循环数
        return false;
    ans[far]=true;//指下一位被遍历
    dfs(far);//搜索下一位
}
int main()
{
    cin>>x;
    for(int i=x+1;;i++)
    {
        int flag=0;
        statistics(i);
        int f=cnt;
        for(int j=1;j<=cnt;j++)
        {
            num[j]=old_num[f];
            f--;
        }//将逆序改为正序
        for(int j=1;j<=cnt;j++)
        {
            if(num[j]==0)
            {
                flag=1;
                break;
            }
            for(int k=1;k<j;k++)
            {
                if(num[j]==num[k])//判断其中每一位是否都不重复
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
               break;
        }
        if(flag)
            continue;
        else
        {
            ans[1]=true;
            if(dfs(1))
            {
                cout<<i;
                break;
            }
        }
        for(int j=1;j<=cnt;j++)
        {
            old_num[j]=0;
            num[j]=0;
            ans[j]=0;
        }//注意一定要清零！！！
    }
    return 0;
}

洛谷 题解 P1467 【循环数 Runaround Numbers】

原文：https://www.cnblogs.com/zyh-cr7/p/12237250.html