时间限制: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; }