时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
小明来到一个由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。
示例1
输入
5 5 1
..S..
.....
.###.
.....
..T..
1 2 3 3
5 5 1
..S..
.....
.###.
.....
..T..
3 3 1 2
5 5 1
S.#..
..#..
###..
.....
....T
0 1 0 2
4 4 2
S#.T
.#.#
.#.#
.#.#
0 0 0 3
2 0 2 2
输出
6
8
-1
3
题意：
一个n*m的地图，S为起点，T为终点，上下左右移动花费为1，传送服务花费为3.地图内有#表示不能走，问从S到T最少花费是多少？
题解：
一个方法是用过bfs做，想想没有传送带就是光搜，有了传送带就用优先队列来换掉广搜的队列，这样保证出队的点都是当前距离起点最近的。
还有个方法就是当做最短路径来做，根据所给的mn矩阵建图，建一个从S到T的图，每个格子当做一个顶点，每个格子与上下左右的格子建立一条权值为1的双向边，当遇到传送带时，建立从入口到出口的单向边，边权为3，然后上最短路板子。
spfa用怕了。。。还是用dijkstra比较安全。。。
代码：
参考代码
bfs：
#include <bits/stdc++.h>
using namespace std;
int const maxn = 300 + 10;
struct node {
int x, y, step;
node(const int &x = 0, const int &y = 0, const int &step = 0) :
x(x), y(y), step(step) {
}
bool operator<(const node & obj) const {
return step > obj.step;
}
};
map<pair<int,int>,pair<int,int>> mv;
int dx[4]={
1,0,-1,0};
int dy[4]={
0,1,0,-1};
int n, m, q;
int vis[maxn][maxn];
char mp[maxn][maxn];
bool check(int tx, int ty) {
if (tx <= 0 || ty <= 0 || tx > n || ty > m) return false;
return true;
}
int bfs(int sx, int sy) {
priority_queue<node> q;
q.emplace(sx, sy, 0);
while (!q.empty()) {
int x = q.top().x, y = q.top().y;
int s = q.top().step;
q.pop();
if (vis[x][y]) {
continue;
}
vis[x][y] = 1;
if (mp[x][y] == 'T') {
return s;
}
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (check(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty]) {
q.emplace(tx, ty, s + 1);
}
}
if (mv.count({
x, y}))
{
int tx = mv[{
x, y}].first;
int ty = mv[{
x, y}].second;
if (check(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty])
{
q.emplace(tx, ty, s + 3);
}
}
}
return -1;
}
int main()
{
while (cin >> n >> m >> q)
{
memset(vis, 0, sizeof(vis));
mv.clear();
int x, y;
for (int i = 1; i <= n; i++)
{
cin >> mp[i] + 1;
for (int j = 1; j <= m; j++)
{
if (mp[i][j] == 'S')
{
x = i, y = j;
}
}
}
while (q--)
{
int x, y, u, v;
cin >> x >> y >> u >> v;
x++, y++, u++, v++;
mv[{
x, y}] = {
u, v};
}
int ans = bfs(x, y);
cout << ans << endl;
}
return 0;
}
dijkstra
代码出处
#include<bits/stdc++.h>
using namespace std;
const int N=301,M=300*300*4+1001;
char a[N][N];
struct node{
int v,w,nex;
}t[M];
int dx[4]={
0,0,-1,1};
int dy[4]={
1,-1,0,0};
bool vis[N*N];int dis[N*N];
int las[N*N],len;
inline void add(int u,int v,int w){
t[++len]=(node){
v,w,las[u]},las[u]=len;
}
inline void dijkstra(int st){
memset(dis,0x3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<pair<int,int> >sp;
dis[st]=0;sp.push(make_pair(0,st));
while(!sp.empty()){
int x=sp.top().second;sp.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=las[x];i;i=t[i].nex){
int v=t[i].v,w=t[i].w;
if(dis[v]>dis[x]+w){
dis[v]=dis[x]+w;
sp.push(make_pair(-dis[v],v));
}
}
}
}
int main(){
int n,m,q;
while(~scanf("%d%d%d",&n,&m,&q)){
memset(las,0,sizeof(las)),len=0;
int sx,sy,tx,ty;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf(" %c",&a[i][j]);
if(a[i][j]=='S'){
sx=i,sy=j;
}
if(a[i][j]=='T'){
tx=i,ty=j;
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i][j]!='#'){
for(int k=0;k<4;++k){
int x=i+dx[k],y=j+dy[k];
if(x&&x<=n&&y&&y<=m&&a[x][y]!='#'){
add((i-1)*m+j,(x-1)*m+y,1);
}
}
}
}
}
for(int i=1;i<=q;++i){
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
++x1,++y1,++x2,++y2;
add((x1-1)*m+y1,(x2-1)*m+y2,3);
}
dijkstra((sx-1)*m+sy);
if(!vis[(tx-1)*m+ty]){
puts("-1");
}else{
printf("%d\n",dis[(tx-1)*m+ty]);
}
}
return 0;
}
京公网安备 11010502036488号