5 条题解

  • 2
    @ 2025-7-18 11:38:30
    #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
      @ 2025-7-18 11:39:52

      #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
        @ 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
          @ 2023-1-6 10:48:07

          经典深搜题

          #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;
          }
          
          • -1
            @ 2022-7-26 21:13:49
            #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

            信息

            ID
            1296
            时间
            1000ms
            内存
            256MiB
            难度
            6
            标签
            递交数
            382
            已通过
            129
            上传者