怎么花最少的钱做网站,著名建站公司,百度广告投放电话,电商网站开发需要掌握哪些知识技能链接#xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
64bit IO Format: %lld题目描述 小明来到一个由n x m个格子组成的迷宫#xff0c;有些格子是陷阱#xff0c;用’#‘表示#xff0c;小明…链接
时间限制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;}
};mappairint,int,pairint,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_queuenode 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 代码出处
#includebits/stdc.h
using namespace std;
const int N301,M300*300*41001;
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_queuepairint,int sp;dis[st]0;sp.push(make_pair(0,st));while(!sp.empty()){int xsp.top().second;sp.pop();if(vis[x])continue;vis[x]1;for(int ilas[x];i;it[i].nex){int vt[i].v,wt[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)),len0;int sx,sy,tx,ty;for(int i1;in;i){for(int j1;jm;j){scanf( %c,a[i][j]);if(a[i][j]S){sxi,syj;}if(a[i][j]T){txi,tyj;}}}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]!#){for(int k0;k4;k){int xidx[k],yjdy[k];if(xxnyyma[x][y]!#){add((i-1)*mj,(x-1)*my,1);}}}}}for(int i1;iq;i){int x1,x2,y1,y2;scanf(%d%d%d%d,x1,y1,x2,y2);x1,y1,x2,y2;add((x1-1)*my1,(x2-1)*my2,3);}dijkstra((sx-1)*msy);if(!vis[(tx-1)*mty]){puts(-1);}else{printf(%d\n,dis[(tx-1)*mty]);}}return 0;
}
