Description

 给你一个n，问能否将1到n这n个整数进行排列，使得这个排列中任意两个相邻的数字和都是平方数。如果能，输出这个排列（如果存在多个，输出字典序最小的），否则输出-1。

 

Input

 输入一个整数n (1 <= n <= 15)

 

Output

 如果存在这样的排列（如果存在多个，输出字典序最小的），输出n个以空格隔开的整数表示这个排列，否则输出-1。

Sample Input

1

Sample Output

1

HINT

 

C++版本一

题解：

求上图的哈密顿路径

只有当n等于1和15时才存在

#include<bits/stdc++.h>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	if(n == 1) printf("1\n"); 
	else if(n == 15) printf("8 1 15 10 6 3 13 12 4 5 11 14 2 7 9\n");
	else printf("-1\n");
	return 0;
}

C++版本二

题解：

BFS

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=10000;
int t,n,m,flag;
int a[N],vis[N];
 
void bfs(int k){
    if(k==n+1){
        int f=1;
        for(int i=1;i<=n-1;i++){
            int tmp=(int)sqrt(a[i]+a[i+1]);
            if(a[i]+a[i+1]!=tmp*tmp){
                f=0;break;
            }
        }
        if(f){
            for(int i=1;i<=n-1;i++)
                printf("%d ",a[i]);
     
            printf("%d\n",a[n]);
            flag=1;
        }
        return;
    }
    for(int i=1;i<=n;i++){
        int tmp=(int)sqrt(i+a[k-1]);
            if(k>1&&i+a[k-1]!=tmp*tmp)
                continue;
        if(vis[i]==0&&flag==0){
            vis[i]=1;
            a[k]=i;
            bfs(k+1);
            vis[i]=0;
        }
    }
}
int main()
{
    flag=0;
    scanf("%d",&n);
    bfs(1);
    if(flag==0)
    printf("%d\n",-1);
    return 0;
}