1 条题解

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

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
     
    char a[150][150];
    //存储到达每个点最少需要多少步
    int d[150][150]; 
    //s1,s2,t1,t2:表示入口和出口 
    int m,n,s1,s2,t1,t2;
    
    //递归求步数 
    void fun(int dep,int i,int j){
    	if(dep < d[i][j]){
    		d[i][j] = dep;
    		if(a[i-1][j] == '.' || a[i-1][j] == 'T') fun(dep+1,i-1,j); 
    		if(a[i+1][j] == '.' || a[i+1][j] == 'T') fun(dep+1,i+1,j);
    		if(a[i][j-1] == '.' || a[i][j-1] == 'T') fun(dep+1,i,j-1);
    		if(a[i][j+1] == '.' || a[i][j+1] == 'T') fun(dep+1,i,j+1);
    	} 
    }
     
    int main(){
        int i,j;
        cin>>n>>m;
    	 
        //.表示能走,#表示不能走 
        for(i = 1;i <= n;i++){
            for(j = 1;j <= m;j++){
                cin>>a[i][j];
                if(a[i][j] == 'S'){
                	s1 = i;
                	s2 = j;
    			}else if(a[i][j] == 'T'){
    				t1 = i;
    				t2 = j;
    			} 
                d[i][j] = INT_MAX;
            }
        }
        
        fun(1,s1,s2);
        
    //    for(i = 1;i <= n;i++){
    //    	for(j = 1;j <= m;j++){
    //    		cout<<d[i][j]<<" ";
    //		}
    //		cout<<endl;
    //	} 
        
        //本题开始不算一步 
    	cout<<d[t1][t2] - 1<<endl; 
    }
    
    
    • 1

    【基础】走出迷宫的最少步数2

    信息

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