额。。这题过的有点悬
USER: Tom Chen [45384401]
TASK: betsy
LANG: C++

Compiling…
Compile: OK

Executing…
Test 1: TEST OK [0.011 secs, 2804 KB]
Test 2: TEST OK [0.000 secs, 2804 KB]
Test 3: TEST OK [0.011 secs, 2804 KB]
Test 4: TEST OK [0.011 secs, 2804 KB]
Test 5: TEST OK [0.000 secs, 2804 KB]
Test 6: TEST OK [0.022 secs, 2804 KB]
Test 7: TEST OK [0.961 secs, 2804 KB]

All tests OK.
时间卡的好紧额囧。。
我只用了两个剪枝，一个是每个除了终点之外的点要一进一出所以要记录相邻的点数，还有一个就是当前点到终点的距离如果小于剩下的点数就剪枝。。
这样都能过囧。。
Code：
/*
PROG: betsy
LANG: C++
ID: Tom Chen
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
using namespace std;
const int maxn=10,di[]={1,0,-1,0},dj[]={0,-1,0,1};
bool vis[maxn][maxn]={0};
int n,ans=0;
int C[maxn][maxn];
int ii,jj;
void show()
{
rep(i,n)
{
rep(j,n) cout<<C[i][j]<<" ";
cout<<endl;
}
}
int Put(int i,int j)
{
int ret=0;
vis[i][j]=true;
rep(d,4)
{
ii=di[d]+i,jj=dj[d]+j;
if(!vis[ii][jj]&&–C[ii][jj]<2&&(ii!=n||jj!=1))
ret++;
}
return ret;
}
void Back(int i,int j)
{
vis[i][j]=false;
rep(d,4)
{
ii=di[d]+i,jj=dj[d]+j;
if(!vis[ii][jj])
++C[ii][jj];
}
}
inline int dist(int a,int b){return a>0?a:-a+b>0?b:-b;}
void dfs(int i,int j,int c)
{
//cout<<i<<" "<<j<<" "<<c<<endl;
//show();
if(n*n-c<dist(i-n,j-1))return;
if(i==n&&j==1)
{
if(c==n*n) ans++;
return;
}
int t=Put(i,j);
if(t<=1)
{
rep(d,4)
{
ii=i+di[d],jj=j+dj[d];
if(!vis[ii][jj]&&(!t||C[ii][jj]<2))
dfs(ii,jj,c+1);
}
}
Back(i,j);
}
int main()
{
freopen("betsy.in","r",stdin);
freopen("betsy.out","w",stdout);
cin>>n;
rep(i,n+2)rep(j,n+2)vis[i][j]=true;
For(i,1,n)For(j,1,n) C[i][j]=4,vis[i][j]=false;
For(i,1,n) C[i][1]=C[1][i]=C[n][i]=C[i][n]=3;
C[1][1]=C[1][n]=C[n][1]=C[n][n]=2;
dfs(1,1,1);
cout<<ans<<endl;
}