HDU 1016 Prime Ring Problem

HDU 1016 Prime Ring Problem

這題我用的是DFS。不多說，看代碼和注釋。

#include
#include
#include
#include
#include
using namespace std;

//因為n<20，所以最大的素數也就是40左右，因此用一個數組來記錄45以內的素數，用於之後的判定。
bool isprime[45]={0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0};
int n;
bool visited[24];//用於標記是否被訪問過
void dfs(int cnt,int id,int ans[])
{
    if(cnt==n+1)
    {
        printf("%d",ans[1]);
        for(int i=2;i<=n;i++)
            printf(" %d",ans[i]);
        printf("\n");
        return;
    }
    for(int i=2;i<=n;i++)
    {
        if(visited[i]||i==id)
            continue;
        visited[i]=true;
        if(cnt==n)//這裡注意要區分是不是到達第n個數，如果到達因為是圓環，所以還要判定和1相加是不是素數。
        {
            int t1=ans[cnt-1]+i;
            int t2=i+1;
            if(isprime[t1]&&isprime[t2])
            {
                ans[cnt]=i;
                dfs(cnt+1,i,ans);
            }
        }
        else//否則就判斷和前一個數相加是不是素數
        {
            int t=ans[cnt-1]+i;
            if(isprime[t])
            {
                ans[cnt]=i;
                dfs(cnt+1,i,ans);
            }
        }
        visited[i]=false;//記得恢復
    }
}
int main()
{
    int k=1;
    while(scanf("%d",&n)!=EOF)
    {
        int ans[25];
        ans[1]=1;
        memset(visited,false,sizeof(visited));
        visited[1]=true;
        printf("Case %d:\n",k++);
        dfs(2,1,ans);
        printf("\n");
    }
    return 0;
}