严禁暴力解决最后一个点！！
题目描述
一个正方形的镇区分为N×N个小方块（1≤N≤7）。农场位于方格的左上角，集市位于左下角。奶牛Bessie穿过小镇。从左上角走到左下角，每次可以走上，下，左，右，但不能走出方格的外面，每个格经过且仅经过一次。当N=3时，贝茜的漫游路径可能如下图所示：
写一个程序，对于给出的N值，计算Bessie从农场走到集市有多少条路径。
输入输出格式
输入格式：
一行，一个整数N。（1≤N≤7）
输出格式：
只有一行。输出一个整数表示路径的数量。
输入输出样例
输入样例：
2
输出样例： 
View Code
1
思路：不可硬搜，可通过出路条数判断方向。
//程序名:新的C++程序 //作者: #include<iostream>using namespace std; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},n,ans,way[8][8];//方向，答案，路线数 bool f[8][8];//是否经过 bool in(int x,int y)//是否在界内 {if(x>=1&&x<=n&&y>=1&&y<=n)return true;return false; } bool must(int x,int y)//出路是否足够 {if(x==n&&y==1){if(way[x][y]==0)return true;//到达终点并且已无出路else return false;}else {if(way[x][y]==1)return true;//未到达终点并且有一条出路else return false;} } void dfs(int x,int y,int d) {if(x==n&&y==1)//到达终点并且全部走完 {if(d==n*n)ans++;return;}f[x][y]=true;//占领该点int p=0,fx,nx,ny;for(int i=0;i<4;i++) {nx=x+dx[i],ny=y+dy[i];if(!in(nx, ny)||f[nx][ny])continue;//出界或已经过way[nx][ny]--;//出路减少if(must(nx,ny))//符合条件的路数（唯一选择） {fx=i;p++;}}if(p==1)dfs(x+dx[fx],y+dy[fx],d+1);//只有一条出路else if(p==0)//如果无唯一选择则全搜 {for(int i=0;i<4;i++) {nx=x+dx[i],ny=y+dy[i];if(!in(nx,ny)||f[nx][ny])continue;dfs(nx,ny,d+1);}}f[x][y]=false;//回溯for(int i=0;i<4;i++) {nx=x+dx[i],ny=y+dy[i];if(!in(nx,ny)||f[nx][ny])continue;way[nx][ny]++;} }int main() {cin>>n;for(int i=1;i<=n;i++)//统计出路 {for(int j=1;j<=n;j++){if(i==1||i==n){if(j==1||j==n)way[i][j]=2;else way[i][j]=3;continue;}if(j==1||j==n){if(i==1||i==n)way[i][j]=2;else way[i][j]=3;continue;}way[i][j]=4;}} dfs(1,1,1);cout<<ans<<endl;return 0; }
