[depth first search] Ji Suan Ke: Betsy's trip

DFS： Start to finish , If you happen to leave at the end n*n Step ,ans++;

If you don't prune , Will timeout

prune ：

1、 Avoid walking into a dead end

 

2、 Avoid forming isolated areas

Code ：

#include<iostream>
using namespace std;
int n;
int ans=0;
bool vis[8][8];

void dfs(int x,int y,int step){
	if(!(x>=0&&y>=0&&x<n&&y<n))return;
	if(vis[x][y]==true)return;
	if(x==n-1&&y==0){
		if(step==n*n-1){
			ans++;
		}
		return;
	}
	if(x==n-1&&vis[x][y+1]==false&&vis[x][y-1]==false&&y-1>=0&&y+1<n||y==n-1&&vis[x+1][y]==false&&vis[x-1][y]==false&&x-1>=0&&x+1<n){
		return;
	}
	vis[x][y]=true; 
	dfs(x+1,y,step+1);
	dfs(x-1,y,step+1);
	dfs(x,y+1,step+1);
	dfs(x,y-1,step+1);
	vis[x][y]=false;
	
}
int main(){
	cin>>n;
	dfs(0,0,0);
	cout<<ans;
} 

  Experience ： Narrow the scope of , Use it well for debugging