搜索与回溯——迷宫问题★★★

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
using namespace std;

const int maxn = 100 + 10;
int n,m;
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int mg[11][11];
int cnt = 0;

void dfs(int x,int y)
{
	if(x == 0 && y == n-1)
	{
		cnt++;
		return;
	}
	int x1,y1;
	for(int i=0;i<8;i++)
	{
		x1 = x + dx[i];
		y1 = y + dy[i];
		if(x1>=0&&x1<n&&y1>=0&&y1<n&&mg[x1][y1]==0)
        {
            mg[x1][y1]=1;
            dfs(x1,y1);
            mg[x1][y1]=0;
        }
	}
}


int main() 
{
	memset(vis,0,sizeof(vis));
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		cin>>mg[i][j];
	mg[0][0] = 1;
	dfs(0,0);
	cout<<cnt<<endl;
	return 0;
}