top1编程
← 返回题目
题解

【入门】古希腊之争(二)

1 条题解

  • 0
    @ 2026-7-28 22:10:18
    #include<bits/stdc++.h>
    using namespace std;
    char  a[30][30];// 存迷宫地图
    int   b[30][30]; 
    //左下右上
    int fx[5]={0,0,1,0,-1};
    int fy[5]={0,-1,0,1, 0};
    int b1,b2,e1,e2,n,m;// b1,b2起点S坐标;e1,e2终点T坐标
    // x,y当前坐标,k走到当前点花费的总时间
    void dfs(int x,int y,int k){
    	b[x][y]=k; // 更新该点最短时间
    	//枚举四个方向
    	for(int i=1;i<=4;i++){
    		int tx=x+fx[i];
    		int ty=y+fy[i];
    		//在边界内并且不是陷阱
    		if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]!='K'){
    			// 遇到墙壁#穿墙,移动1+破墙+1,总共+2时间
    			if(a[tx][ty]=='#'&&b[tx][ty]>k+2){
    				dfs(tx,ty,k+2);
    			}
    			// 空地./S/T:正常走路只+1时间
    			else if(b[tx][ty]>k+1){
    				dfs(tx,ty,k+1);         
    			}
    		}
    	}	
    }
    
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>a[i][j];
    			b[i][j]=INT_MAX; // 最短时间初始无穷大,表示未到达
    			if(a[i][j]=='S'){//记录起点
    				b1=i;b2=j;
    			}
    			if(a[i][j]=='T'){//记录终点
    				e1=i;e2=j;
    			}
    		}
    	}
    	dfs(b1,b2,0);//起点耗时初始为0
    	//终点仍无穷大=走不到
    	if(b[e1][e2]==INT_MAX){
    		cout<<"-1";
    	}else{
    		cout<<b[e1][e2];
    	}
    	return 0;
    }
    
    • 1