6 条题解
-
2
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e2+10; int n,a[N][N],ans; int dx[]={-1,-1,-1, 0, 0, 1, 1, 1}; int dy[]={-1, 0, 1,-1, 1,-1, 0, 1}; bool check(int x,int y){ if(x>=1&&x<=n&&y>=1&&y<=n&&a[x][y]==0){ return 1; } return 0; } void dfs(int x,int y){ if(x==1&&y==n){ ans++; return; } a[x][y]=1; for(int i=0;i<=7;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(check(xx,yy)){ dfs(xx,yy); a[xx][yy]=0; } } } signed main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } dfs(1,1); cout<<ans; return 0; } -
0
#define int long long using namespace std; const int N=1e2+10; int n,a[N][N],ans; int dx[]={-1,-1,-1, 0, 0, 1, 1, 1}; int dy[]={-1, 0, 1,-1, 1,-1, 0, 1}; bool check(int x,int y){ if(x>=1&&x<=n&&y>=1&&y<=n&&a[x][y]==0){ return 1; } return 0; } void dfs(int x,int y){ if(x==1&&y==n){ ans++; return; } a[x][y]=1; for(int i=0;i<=7;i++){ int xx=x+dx[i]; int yy=y+dy[i]; if(check(xx,yy)){ dfs(xx,yy); a[xx][yy]=0; } } } signed main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } dfs(1,1); cout<<ans; return 0; } -
0
#include #include <string.h> #include <math.h> #include #include #include #include #include #include #include #include <stdio.h> #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include <complex.h> #include <fenv.h> #include <inttypes.h> #include <stdbool.h> #include <stdint.h> #include <tgmath.h> #define int long long using namespace std; const int N=10+10; int n,s[N][N],ans; int da[]={-1,-1,-1,0,0,1,1,1}; int db[]={-1,0,1,-1,1,-1,0,1}; bool check(int a,int b) { if(a>=1&&b>=1&&a<=n&&b<=n&&s[a][b]0) return 1; return 0; } void dfs(int a,int b) { if(a1&&b==n) { ans++; return ; } s[a][b]=1; for(int i=0;i<=7;i++) { int aa=a+da[i]; int bb=b+db[i]; if(check(aa,bb)) { dfs(aa,bb); s[aa][bb]=0; } } } signed main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>s[i][j]; dfs(1,1); cout<<ans; return 0; }
-
-1
zengzhiyuan
LV 9
@ 2024-6-23 11:10:37
#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; } -
-1
经典深搜题
#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; } -
-2
#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; }
- 1