基础bfs maze ,麻烦好心大佬给我看看哪里错了
链接:https://ac.nowcoder.com/acm/problem/15665
一个格子可能既有多个入口,又有多个出口,小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的,因为有的传送阵的出口在陷阱里,如果小明使用这样的传送阵,那他就会死亡。也有一些传送阵的入口在陷阱里,这样的传送阵是没有用的,因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。
题目描述
小明来到一个由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;
}
上海得物信息集团有限公司公司福利 1202人发布
查看5道真题和解析