传送爸爸

传送爸爸\operatorname{传送爸爸}

传送爸爸
题目链接:

luoguT145195\operatorname{luogu\ T145195}

luoguT145195 /

SSL比赛1515\operatorname{SSL比赛\ 1515}

SSL比赛1515
题目背景

wdyhy 非常喜欢他的爸爸们,所以只要让爸爸们永远呆在 wdyhy 的迷宫里, wdyhy 就可以永远爱着他们啦!
传送爸爸

题目

wdyhy 有一个

RR

R 行

CC

C 列的迷宫,每一个小格有一个字符。

#\#

# (number sign) 表⽰一个墙块,

..

. (dot) 表⽰一块空地,

SS

S (uppercase letter s) 表⽰你现在的位置,

CC

C (uppercase letter c) 表⽰爸爸现在的位置。

你只能通过空地,并且,只有当两块空地有相临边时,你才可以从其中一个走向另一个。特别的,描述在地图里的矩形区域完全被墙块包围。

为了能够更快的到达爸爸的位置,你从迦勒底获得了一个传送枪,它的操作方式如下:任意时候它都可以向上下左右四个方向发射传送门。当一个传送门以某一特定方向发送时,它会沿着此方向飞出直到碰到第一个墙块。当发生上述情况时,一个传送门就会贴在面对着你那面的墙块上。

任意时刻最多只能存在两个传送门。如果迷宫里已经有了两个传送门,那么你可以使用传送枪的另一个功能马上移除一个(由你选定)。向一个已经存在的传送门发射时,后发射的传送门会替代原有的,所以每个墙块的每一面最多只会存在一个传送门。注意,可以存在两个传送门在同一墙块上,只要他们所朝方向不同。

当迷宫中存在两个传送门时,你可以通过它们传送自己。当你站在一个传送门旁时,你可以走进传送门然后从另一个传送门走出来到它相邻的空地,这样耗费的时间与你走相邻两个空地的时间是相同的。

你可以假设发射传送门不会耗费任何时间,走相邻两个空地和通过传送门的时间都是

11

1 。 那么,你最少需要多长时间才能到爸爸那里。

输入

输入文件第一行包括两个整数:地图的行数

RR

R 和列数

CC

C 。接下来的

RR

R 行描述这个地图。每一行包括

CC

C 个字符:

#.S\#.S

#.S 或

CC

C (含义已在上文描述)。

输出

输出一个整数——从你现在位置出发到达爸爸的位置所需要的最少时间。

样例输入

4 4
.#.C
.#.#
....
S...

样例输出

4

样例解释

传送爸爸

数据范围

传送爸爸

思路

这道题其实可以用

spfaspfa

spfa 最短路来解决,但是建图很 nb 。

我们可以知道,一个地方可以直接走到另外一个地方,也可以走传送门。
直接走很好搞,但是走传送门怎么搞呢?
我们就可以看出,我们可以走到四个方向第一个碰到墙壁的地方,但是自己要走多少呢?
其实就是这四个方向的墙壁中距离他最短的那个。
我这里就直接暴力去找,然后记忆化。
(不记忆化会超时)

然后我们就把可以那八个走的地方连边,边权就是要自己走的步数。
然后跑一遍最短路,起点是什么就不用说了吧。
最后输出起点到终点的距离就是了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define rr register

using 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+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏