题解
【入门】古希腊之争(二)
1 条题解
-
0
#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