1 条题解

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

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    
    char s[20][20];//存放迷宫
    bool f[20][20];//标记是否走过
    int r[10000][2];//存放Mitch走过的路径
    //右,下,左,上 
    int fx[] = {0,1,0,-1};
    int fy[] = {1,0,-1,0};
    int n,m,total;
    bool flag;//标记是否存在走出迷宫的路径 
    
    //输出路径 
    void print(int x){
    	int i;
    	total++;
    	cout<<total<<":";
    	flag = true;//有走出迷宫的路径 
    	for(i = 1;i <= x;i++){
    		if(i != x){
    			cout<<r[i][1]<<","<<r[i][2]<<"->";
    		}else{
    			cout<<r[i][1]<<","<<r[i][2]<<endl;
    		}
    	}
    }
    
    //k表示数组填到的下标 
    void fun(int k){
    	int i,j,dx,dy;
    	//遍历所有方向
    	for(i = 0;i < 4;i++){
    		dx = r[k-1][1] + fx[i];
    		dy = r[k-1][2] + fy[i];
    		
    		//判断新点是否可达
    		if(dx >= 1 && dx <= n && dy >= 1 && dy <= m && s[dx][dy] == 'o' && f[dx][dy] == false){
    			r[k][1] = dx;
    			r[k][2] = dy;
    			f[dx][dy] = true;//标记该点走过
    			
    			//到目的地,输出 
    			if(dx == n && dy == m){
    				print(k);
    			}else{
    				fun(k+1);
    			} 
    			
    			f[dx][dy] = false;//回溯 
    		} 
    	} 
    } 
    
    int main(){
    	cin>>n>>m;
    	int i,j;
    	for(i = 1;i <= n;i++){
    		for(j = 1;j <= m;j++){
    			cin>>s[i][j];
    		}
    	}
    	
    	//起始点 
    	r[1][1] = 1;
    	r[1][2] = 1; 
    	f[1][1] = true;//标记起始点走过了
    	fun(2); 
    	
    	if(flag == false){
    		cout<<"no"<<endl;
    	} 
    	
    }
    
    
    • 1

    信息

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