欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

传送爸爸

程序员文章站 2022-03-30 18:34:53
SSL比赛 1515.传送爸爸,luogu T145195 【2020.8.23NOIP模拟赛】传送爸爸,一个巧妙的建图然后spfa最短路...

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

题目链接:luogu T145195\operatorname{luogu\ T145195} / SSL比赛 1515\operatorname{SSL比赛\ 1515}

题目背景

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

题目

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

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

.. (dot) 表⽰一块空地,

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

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

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

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

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

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

你可以假设发射传送门不会耗费任何时间,走相邻两个空地和通过传送门的时间都是 11 。 那么,你最少需要多长时间才能到爸爸那里。

输入

输入文件第一行包括两个整数:地图的行数 RR 和列数 CC 。接下来的 RR 行描述这个地图。每一行包括 CC 个字符: #.S\#.SCC (含义已在上文描述)。

输出

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

样例输入

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

样例输出

4

样例解释

传送爸爸

数据范围

传送爸爸

思路

这道题其实可以用 spfaspfa 最短路来解决,但是建图很 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://blog.csdn.net/weixin_43346722/article/details/108185960