1 条题解

  • 0
    @ 2023-6-11 12:17:08

    C :

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<ctype.h>
    #include<math.h>
    int a[101][101],n,sx,sy,ex,ey,f;//f到达标志 
    void dfs(int i,int j){
    	a[i][j] = 1;
    	if(i==ex && j==ey){
    		f = 1;
    		return;
    	}
    	//不能超越格子,必须能通行,没有一条到终点 
    	if(i-1>=1 && i-1<=n && a[i-1][j]==0 && f==0) dfs(i-1,j);
    	if(i+1>=1 && i+1<=n && a[i+1][j]==0 && f==0) dfs(i+1,j);
    	if(j-1>=1 && j-1<=n && a[i][j-1]==0 && f==0) dfs(i,j-1);
    	if(j+1>=1 && j+1<=n && a[i][j+1]==0 && f==0) dfs(i,j+1);
    } 
    int main(){
    	int i,j;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++){
    		for(j=1;j<=n;j++){
    			scanf("%d",&a[i][j]);
    		}
    	}
    	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    	//递归深搜之前判断起点、终点是否有效 
    	if(a[sx][sy]==1||a[ex][ey]==1) {
    		printf("NO");
    		return 0;
    	} 
    	//如果有效开始递归 
    	dfs(sx,sy);
    	//到底有没有到达终点 
    	if(f==0) printf("NO");
    	else printf("YES");
    	return 0;
    }
    
    

    C++ :

    #include <iostream>
    using namespace std;
    
    int a[150][150],n,x1,y1,x2,y2;
    bool f = false;//表示有没有走到 
    
    //从x、y点开始逐步探测 
    void num(int x,int y){
    	if(x == x2 && y == y2){
    		f = true;
    	}else{
    		a[x][y] = 1;//探测过的点,设置为不可探测,防止重复的探测 
    		//上下左右探测,且不越界 
    		if(x - 1 >= 1 && a[x - 1][y] == 0) num(x-1,y);
    		if(x + 1 <= n && a[x + 1][y] == 0) num(x+1,y);
    		if(y - 1 >= 1 && a[x][y - 1] == 0) num(x,y - 1);
    		if(y + 1 <= n && a[x][y + 1] == 0) num(x,y + 1);
    	}
    } 
    
    int main(){
    	int i,j;
    	cin>>n;
    	//0表示能走,1表示不能走 
    	for(i = 1;i <= n;i++){
    		for(j = 1;j <= n;j++){
    			cin>>a[i][j];
    		}
    	}
    	cin>>x1>>y1>>x2>>y2;
    	
    	//如果起止点有1,则不需要探测 
    	if(a[x1][y1] == 1 || a[x2][y2] == 1){
    		cout<<"NO"<<endl; 
    	}else{
    		num(x1,y1);
    		//探测完测试,如果走到了 
    		if(f == true){
    			cout<<"YES"<<endl; 
    		}else{
    			cout<<"NO"<<endl;
    		}
    	} 
    }
    
    
    • 1

    信息

    ID
    2350
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者