信息
- ID
- 1296
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 299
- 已通过
- 91
- 上传者
经典深搜题
#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;
}