经典深搜题

#include<bits/stdc++.h>
using namespace std;
int n,a,cnt;
bool qp[15][15];
void dfs(int x,int y)
{
	if(qp[x][y]==false)return;
	if(x==1&&y==n)
	{
		cnt++;
		return;
	}
	qp[x][y]=false;
	dfs(x+1,y+1);
	dfs(x+1,y-1);
	dfs(x-1,y-1);
	dfs(x-1,y+1);
	dfs(x,y+1);
	dfs(x,y-1);
	dfs(x+1,y);
	dfs(x-1,y);
	qp[x][y]=true;
}
int main()
{
	memset(qp,false,sizeof(qp));
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a;
			if(a==1)continue;
			qp[i][j]=true;
		}
	}
	dfs(1,1);
	cout<<cnt;
	return 0;
}

#include<bits/stdc++.h>
using namespace std; 
int a[10000][10000],cur[10000][10000];
int n;
int vis[8][2] = {{1,0},{1,1},{1,-1},{-1,0},{-1,1},{-1,-1},{0,1},{0,-1}};
int cnt = 0;
void dfs(int x, int y){
	
	if(x == 1 && y == n){
		cnt++;
		return;
	}
	for(int i = 0;i < 8;i++){
		if(cur[x + vis[i][0]][y + vis[i][1]] == 0 && a[x + vis[i][0]][y + vis[i][1]] == 1){
			cur[x + vis[i][0]][y + vis[i][1]] = 1;
			dfs(x + vis[i][0],y + vis[i][1]);
			cur[x + vis[i][0]][y + vis[i][1]] = 0;
		}
	}
}
int main(){
	
	cin >> n;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			cin >> a[i][j];
			if(a[i][j] == 1){
				a[i][j] = 0;
			}
			else{
				a[i][j] = 1;
			}
		}
	}
	cur[1][1] = 1;
	dfs(1,1);
	cout << cnt;
	
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int N=25;
int a[N][N]; /*构建矩阵*/
int n;
int sum=0;
void dfs(int x,int y){
    if(x==1&&y==n) sum++;                   /*返回条件，注意是到右上的点*/
    else {
        if(x+1<=n&&y+1<=n&&a[x*2][y*2]<=0&&
           !a[(x+1)*2-1][(y+1)*2-1]){       /*可以通过的条件，用数组存储运动更好*/
            a[(x+1)*2-1][(y+1)*2-1]=1;      /*点的标记*/
            a[x*2][y*2]=1;                  /*点与点之间状态，*/
            dfs(x+1,y+1);                   /*注意：对角线经过的点状态是不同的，*/
            a[(x+1)*2-1][(y+1)*2-1]=0;      /*下面是用-1代表右上角与左下角的运动，*/        
            a[x*2][y*2]=0;                  /*1代表左上角与右下角的运动*/
        }
        if(y+1<=n&&a[x*2-1][2*y]==0&&
           !a[x*2-1][(y+1)*2-1]){
            a[x*2-1][(y+1)*2-1]=1;
            a[x*2-1][2*y]=1;
            dfs(x,y+1);
            a[x*2-1][(y+1)*2-1]=0;
            a[x*2-1][2*y]=0;
        }
        if(x-1>=1&&y+1<=n&&a[(x-1)*2][y*2]>=0&&
           !a[(x-1)*2-1][(y+1)*2-1]){
            a[(x-1)*2-1][(y+1)*2-1]=1;
            a[(x-1)*2][y*2]=-1;             /*左下到右上*/
            dfs(x-1,y+1);
            a[(x-1)*2-1][(y+1)*2-1]=0;
            a[(x-1)*2][y*2]=0;
        }
        if(x+1<=n&&a[x*2][2*y-1]==0&&
           !a[(x+1)*2-1][y*2-1]){
            a[(x+1)*2-1][y*2-1]=1;
            a[x*2][2*y-1]=1;
            dfs(x+1,y);
            a[(x+1)*2-1][y*2-1]=0;
            a[x*2][2*y-1]=0;
        }
        if(x-1>=1&&a[(x-1)*2][2*y-1]==0&&
           !a[(x-1)*2-1][y*2-1]){
            a[(x-1)*2-1][y*2-1]=1;
            a[(x-1)*2][2*y-1]=1;
            dfs(x-1,y);
            a[(x-1)*2][2*y-1]=0;
            a[(x-1)*2-1][y*2-1]=0;
        }

        if(y-1>=1&&a[2*x-1][2*y-2]==0&&
           !a[x*2-1][(y-1)*2-1]){
            a[x*2-1][(y-1)*2-1]=1;
            a[2*x-1][2*y-2]=1;
            dfs(x,y-1);
           a[x*2-1][(y-1)*2-1]=0;
            a[2*x-1][2*y-2]=0;
        }
        if(x+1<=n&&y-1>=1&&a[x*2][(y-1)*2]>=0&&
           !a[(x+1)*2-1][(y-1)*2-1]){
            a[(x+1)*2-1][(y-1)*2-1]=1;
            a[x*2][(y-1)*2]=-1;             /*右上到左下*/
            dfs(x+1,y-1);
            a[(x+1)*2-1][(y-1)*2-1]=0;
            a[x*2][(y-1)*2]=0;
        }

        if(x-1>=1&&y-1>=1&&a[(x-1)*2][(y-1)*2]<=0&&
           !a[(x-1)*2-1][(y-1)*2-1]){
            a[(x-1)*2-1][(y-1)*2-1]=1;
            a[(x-1)*2][(y-1)*2]=1;
            dfs(x-1,y-1);
            a[(x-1)*2-1][(y-1)*2-1]=0;
            a[(x-1)*2][(y-1)*2]=0;
        }
    }
}
int main()
{
    sum=0;
    scanf("%d",&n);
    memset(a,0,sizeof(a));                 /*矩阵清零*/
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[2*i-1][2*j-1]);
    a[1][1]=1;
    dfs(1,1);                              /*调用递归*/
    printf("%d\n",sum);
    return 0;
}