传送爸爸
题目链接:
luoguT145195 /
SSL比赛1515
题目背景
wdyhy 非常喜欢他的爸爸们,所以只要让爸爸们永远呆在 wdyhy 的迷宫里, wdyhy 就可以永远爱着他们啦!
题目
wdyhy 有一个
R 行
C 列的迷宫,每一个小格有一个字符。
# (number sign) 表⽰一个墙块,
. (dot) 表⽰一块空地,
S (uppercase letter s) 表⽰你现在的位置,
C (uppercase letter c) 表⽰爸爸现在的位置。
你只能通过空地,并且,只有当两块空地有相临边时,你才可以从其中一个走向另一个。特别的,描述在地图里的矩形区域完全被墙块包围。
为了能够更快的到达爸爸的位置,你从迦勒底获得了一个传送枪,它的操作方式如下:任意时候它都可以向上下左右四个方向发射传送门。当一个传送门以某一特定方向发送时,它会沿着此方向飞出直到碰到第一个墙块。当发生上述情况时,一个传送门就会贴在面对着你那面的墙块上。
任意时刻最多只能存在两个传送门。如果迷宫里已经有了两个传送门,那么你可以使用传送枪的另一个功能马上移除一个(由你选定)。向一个已经存在的传送门发射时,后发射的传送门会替代原有的,所以每个墙块的每一面最多只会存在一个传送门。注意,可以存在两个传送门在同一墙块上,只要他们所朝方向不同。
当迷宫中存在两个传送门时,你可以通过它们传送自己。当你站在一个传送门旁时,你可以走进传送门然后从另一个传送门走出来到它相邻的空地,这样耗费的时间与你走相邻两个空地的时间是相同的。
你可以假设发射传送门不会耗费任何时间,走相邻两个空地和通过传送门的时间都是
1 。 那么,你最少需要多长时间才能到爸爸那里。
输入
输入文件第一行包括两个整数:地图的行数
R 和列数
C 。接下来的
R 行描述这个地图。每一行包括
C 个字符:
#.S 或
C (含义已在上文描述)。
输出
输出一个整数——从你现在位置出发到达爸爸的位置所需要的最少时间。
样例输入
4 4
.#.C
.#.#
....
S...
样例输出4
样例解释
数据范围
思路
这道题其实可以用
spfa 最短路来解决,但是建图很 nb 。
我们可以知道,一个地方可以直接走到另外一个地方,也可以走传送门。
直接走很好搞,但是走传送门怎么搞呢?
我们就可以看出,我们可以走到四个方向第一个碰到墙壁的地方,但是自己要走多少呢?
其实就是这四个方向的墙壁中距离他最短的那个。
我这里就直接暴力去找,然后记忆化。
(不记忆化会超时)然后我们就把可以那八个走的地方连边,边权就是要自己走的步数。
然后跑一遍最短路,起点是什么就不用说了吧。
最后输出起点到终点的距离就是了。代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define rr registerusing namespace std;
struct node {
int x, to, nxt;
}e[8000001];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, s, t, le[1000001], chong[4], KK, dis[1000001];
int rem[4][1000001], end[4][1000001];//记忆化
bool go[1001][1001], in[1000001];
char c;bool check(int x, int y) {//判断是否在图上
if (x < 1 || x > n) return 0;
if (y < 1 || y > m) return 0;
return 1;
}int getnum(int x, int y) {//找到图上每个点的编号
return (x - 1) * m + y;
}void add(int x, int y, int z) {//建图
e[++KK] = (node){z, y, le[x]}; le[x] = KK;
}int dfs(int x, int y, int pla) {//找到能射到的地方
if (go[x][y] || !check(x, y)) {
chong[pla] = getnum(x - dx[pla], y - dy[pla]);
end[pla][getnum(x, y)] = chong[pla];
return rem[pla][getnum(x, y)] = 0;
}
if (rem[pla][getnum(x, y)]) {
chong[pla] = end[pla][getnum(x, y)];
return rem[pla][getnum(x, y)];
}
int re = dfs(x + dx[pla], y + dy[pla], pla) + 1;
end[pla][getnum(x, y)] = end[pla][getnum(x + dx[pla], y + dy[pla])];
return rem[pla][getnum(x, y)] = re;
}void spfa() {//spfa跑最短路
queue <int> q;
q.push(s);
in[s] = 1;
memset(dis, 0x7f, sizeof(dis));
dis[s] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = le[now]; i; i = e[i].nxt)
if (dis[e[i].to] > dis[now] + e[i].x) {
dis[e[i].to] = dis[now] + e[i].x;
if (!in[e[i].to]) {
in[e[i].to] = 1;
q.push(e[i].to);
}
}
in[now] = 0;
}
}int main() {
scanf("%d %d", &n, &m);//读入
for (rr int i = 1; i <= n; i++)
for (rr int j = 1; j <= m; j++) {
c = getchar();
while (c != '.' && c != '#' && c != 'C' && c != 'S') c = getchar();
if (c == '#') go[i][j] = 1;//判断是不是墙
else {
if (c == 'S') s = (i - 1) * m + j;//记录起点终点的编号
else if (c == 'C') t = (i - 1) * m + j;
}
}for (rr int i = 1; i <= n; i++)
for (rr int j = 1; j <= m; j++) {//枚举每个点
if (go[i][j]) continue;//要不是墙
int start = getnum(i, j), far = 2147483647;
for (int k = 0; k < 4; k++) {//四个方向
far = min(far, dfs(i + dx[k], j + dy[k], k) + 1);//求出四个方向离墙的距离
if (!go[i + dx[k]][j + dy[k]] && check(i + dx[k], j + dy[k])) add(start, getnum(i + dx[k], j + dy[k]), 1);//只普通的走一步
}
for (int k = 0; k < 4; k++)
if (start != chong[k])
add(start, chong[k], far);//传送
}spfa();//spfa跑最短路
printf("%d", dis[t]);//输出
return 0;
}
原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说
免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。
您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 传送爸爸
关注我们小说电影免费看关注我们,获取更多的全网素材资源,有趣有料!120000+人已关注
评论抢沙发