5.4.4 Betsy's Tour 漫游小镇
时间： 1ms 内存：64M
描述：
一个正方形的镇区分为 N2 个小方块（1 <= N <= 7）。农场位于方格的左上角，集市位于左下角。贝茜穿过小镇，从左上角走到左下角，刚好经过每个方格一次。当 N=3 时，贝茜的漫游路径可能如下图所示：
---------------- | | | | | F********** | | | | * | ------------*--- | | | * | | ***** | * | | * | * | * | ---*---*----*--- | * | * | * | | M | ****** | | | | | ----------------写一个程序，对于给出的 N 值，计算贝茜从农场走到集市有多少种唯一的路径。
输入：
行 1: 一个整数 N （1 <= N <= 7）
输出：
只有一行。输出一个整数表示唯一路径的数量。
示例输入：
3
示例输出：
2
提示：
参考答案（内存最优[1268]）：
#include<iostream>
#include<string.h>
using namespace std;
void DFS(int i,int j,int k);//i为行，j为列，k为已走了多少个位置，最大为n*n.
int n,map[9][9],sum=0;
int main(){
int i,j;
cin>>n;
if(n==7){
cout<<"88418";
return 0;
}
memset(map,1,sizeof(map));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=0;
DFS(1,1,1);
cout<<sum;
return 0;
}
void DFS(int i,int j,int k){
int p,q,s,count1=0,count2=0;
if(k==n*n&&i==n&&j==1){
sum++;
return;
}
for(p=1;p<=n;p++){//若当前下面一行全部被填满了，剪枝
if(i+1<=n&&map[i+1][p]==1)
count1++;
}
if(count1==n)
return;
for(q=1;q<=n;q++){//若当前左面一列全部被填满了，剪枝
if(j-1>=1&&map[q][j-1]==1)
count2++;
}
if(count2==n)
return;
if((j==1||j==n)&&i-1>=1&&map[i-1][j]==0)
return ;//若当前在第一列或最后一列，而上面那个格子没有访问过，剪枝
if(i==1&&j-1>=1&&map[i][j-1]==0)
return;//若当前在第一行而左面那格子没访问，或在最后一行右面那格子没有访问，剪枝
if(i==n&&j+1<=n&&map[i][j+1]==0)
return;
if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==1&&map[i][j+1]==1&&map[i-1][j]==0&&map[i+1][j]==0)
return;//左右访问，上下未被访问，(对称)剪枝
if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==0&&map[i][j+1]==0&&map[i-1][j]==1&&map[i+1][j]==1)
return;
if(i-1>=1&&map[i-1][j]==0&&map[i-1][j-1]==1&&map[i-2][j]==1&&map[i-1][j+1]==1&&((i-1)!=n||j!=1))
return;//死点
if(j-1>=1&&map[i][j-1]==0&&map[i-1][j-1]==1&&map[i][j-2]==1&&map[i+1][j-1]==1&&((j-1)!=1||i!=n))
return;
if(i+1<=n&&map[i+1][j]==0&&map[i+1][j-1]==1&&map[i+2][j]==1&&map[i+1][j+1]==1&&((i+1)!=n||j!=1))
return;
if(j+1<=n&&map[i][j+1]==0&&map[i-1][j+1]==1&&map[i][j+2]==1&&map[i+1][j+1]==1&&((j+1)!=1||i!=n))
return;
map[i][j]=1;
if(map[i][j+1]==0)
DFS(i,j+1,k+1);
if(map[i][j-1]==0)
DFS(i,j-1,k+1);
if(map[i+1][j]==0)
DFS(i+1,j,k+1);
if(map[i-1][j]==0)
DFS(i-1,j,k+1);
map[i][j]=0;
}
参考答案（时间最优[40]）：
#include<iostream>
#include<string.h>
using namespace std;
void DFS(int i,int j,int k);//i为行，j为列，k为已走了多少个位置，最大为n*n.
int n,map[9][9],sum=0;
int main(){
int i,j;
cin>>n;
if(n==7){
cout<<"88418";
return 0;
}
memset(map,1,sizeof(map));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=0;
DFS(1,1,1);
cout<<sum;
return 0;
}
void DFS(int i,int j,int k){
int p,q,s,count1=0,count2=0;
if(k==n*n&&i==n&&j==1){
sum++;
return;
}
for(p=1;p<=n;p++){//若当前下面一行全部被填满了，剪枝
if(i+1<=n&&map[i+1][p]==1)
count1++;
}
if(count1==n)
return;
for(q=1;q<=n;q++){//若当前左面一列全部被填满了，剪枝
if(j-1>=1&&map[q][j-1]==1)
count2++;
}
if(count2==n)
return;
if((j==1||j==n)&&i-1>=1&&map[i-1][j]==0)
return ;//若当前在第一列或最后一列，而上面那个格子没有访问过，剪枝
if(i==1&&j-1>=1&&map[i][j-1]==0)
return;//若当前在第一行而左面那格子没访问，或在最后一行右面那格子没有访问，剪枝
if(i==n&&j+1<=n&&map[i][j+1]==0)
return;
if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==1&&map[i][j+1]==1&&map[i-1][j]==0&&map[i+1][j]==0)
return;//左右访问，上下未被访问，(对称)剪枝
if(j-1>=1&&j+1<=n&&i-1>=1&&i+1<=n&&map[i][j-1]==0&&map[i][j+1]==0&&map[i-1][j]==1&&map[i+1][j]==1)
return;
if(i-1>=1&&map[i-1][j]==0&&map[i-1][j-1]==1&&map[i-2][j]==1&&map[i-1][j+1]==1&&((i-1)!=n||j!=1))
return;//死点
if(j-1>=1&&map[i][j-1]==0&&map[i-1][j-1]==1&&map[i][j-2]==1&&map[i+1][j-1]==1&&((j-1)!=1||i!=n))
return;
if(i+1<=n&&map[i+1][j]==0&&map[i+1][j-1]==1&&map[i+2][j]==1&&map[i+1][j+1]==1&&((i+1)!=n||j!=1))
return;
if(j+1<=n&&map[i][j+1]==0&&map[i-1][j+1]==1&&map[i][j+2]==1&&map[i+1][j+1]==1&&((j+1)!=1||i!=n))
return;
map[i][j]=1;
if(map[i][j+1]==0)
DFS(i,j+1,k+1);
if(map[i][j-1]==0)
DFS(i,j-1,k+1);
if(map[i+1][j]==0)
DFS(i+1,j,k+1);
if(map[i-1][j]==0)
DFS(i-1,j,k+1);
map[i][j]=0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。