题目描述
小明来到一个由n x m个格子组成的迷宫,有些格子是陷阱,用'#'表示,小明进入陷阱就会死亡,'.'表示没有陷阱。小明所在的位置用'S'表示,目的地用'T'表示。
小明只能向上下左右相邻的格子移动,每移动一次花费1秒。
有q个单向传送阵,每个传送阵各有一个入口和一个出口,入口和出口都在迷宫的格子里,当走到或被传送到一个有传送阵入口的格子时,小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里,这个过程会花费3秒;如果不开启传送阵,将不会发生任何事情,小明可以继续向上下左右四个方向移动。
输入描述:
有多组数据。对于每组数据: 第一行有三个整数n,m,q(2≤ n,m≤300,0≤ q ≤ 1000)。 接下来是一个n行m列的矩阵,表示迷宫。 最后q行,每行四个整数x1,y1,x2,y2(0≤ x1,x2< n,0≤ y1,y2< m),表示一个传送阵的入口在x1行y1列,出口在x2行y2列。
输出描述:
如果小明能够活着到达目的地,则输出最短时间,否则输出-1。
#include<bits/stdc++.h> using namespace std; const int N = 303; char mp[N][N];//迷宫 int visit[N][N];//判断是否走过,1走过,0未走 int Qx[N];//传送门 x坐标 int Qy[N];//传送门y坐标 int n,m;//迷宫:n行,m列 int q;//传送门个数 //左下右上四个方位 int dx[4]={0,1,0,-1}; int dy[4]={-1,0,1,0}; struct Time { int x; int y; int time; }; int bfs(int sx,int sy,int ex,int ey) { queue<Time>qu;//结构型队列 if(mp[sx][sy]=='#') return -1;//起点为陷阱 qu.push(Time{sx,sy,0});//最初,小明在sx,sy处,所用时间为0 while(!qu.empty()) { Time s = qu.front(); qu.pop();//出队 if(s.x==ex&&s.y==ey) { return s.time;//如果到达终点则返回所用时间 } Time next;//下一个位置 //要么走传送门,走传送门要注意 终点是否为陷阱 //接下来有两种选择,要么上下左右走 if(Qx[s.x]!=-1&&Qy[s.y]!=-1&&mp[Qx[s.x]][Qy[s.y]]!='#' &&visit[Qx[s.x]][Qy[s.y]]==0&&mp[s.x][s.y]!='#')//第一种 //如果不为-1那么这个位置肯定有传送门, { //再判断 出口是否为陷阱, //再判断是否走过 //由于传送们的坐标肯定在迷宫内,则不需要判断越界 // 下一个坐标就是传送门的终点 next.x = Qx[s.x]; next.y = Qy[s.y]; next.time = s.time + 3; visit[next.x][next.y] = 1;//走过 qu.push(next); } for(int i=0;i<4;i++) { //上第二种,下左右走 next.x = s.x + dx[i]; next.y = s.y + dy[i]; next.time = s.time + 1; //首先判断是否越界 或者是否是陷阱 if(next.x<0||next.x>n||next.y<0||next.y>m||mp[next.x ][next.y]=='#') continue; //再判断是否走过 if(visit[next.x][next.y ]==1) continue; visit[next.x][next.y] = 1; qu.push(next); } // cout<<"a"<<endl; } return -1;//无法走到终点 } int main() { while(cin>>n>>m>>q) //多组出入 { int sx,sy;//起点 int ex,ey;//终点 //输入迷宫 for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>mp[i][j]; if(mp[i][j]=='S') { sx = i; sy = j;//记录起点坐标 } if(mp[i][j]=='T') { ex = i; ey = j;//记录终点坐标 } } } //输入传送门位置 int qsx,qsy;//传送门 起点坐标 int qex,qey;//传送门终点坐标 memset(visit,0,sizeof(visit));//利用memset函数,全部标记为0,表示为走过 memset(Qx,-1,sizeof(Qx)); memset(Qy,-1,sizeof(Qy)); for(int i=1;i<=q;i++)//输入传送门 { cin>>qsx>>qsy>>qex>>qey; Qx[qsx] = qex; Qy[qsy] = qey;//表示从点(qsx,qsy)通向点(qex,qey) } visit[sx][sy] = 1;//起点当然走过啦 int ans = bfs(sx,sy,ex,ey);//调用函数,进行bfs操作 cout<<ans<<endl; } return 0; }
全部评论
(0) 回帖