传送爸爸
题目链接：

luoguT145195 /

SSL比赛1515
题目背景

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

题目

wdyhy 有一个

R 行

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

$\mathrm{\#}$

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

$\mathrm{.}$

. (dot) 表⽰一块空地，

$S$

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

$C$

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

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

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

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

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

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

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

输入

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

R 和列数

C 。接下来的

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

C 个字符：

#.S 或

C （含义已在上文描述）。

输出

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

样例输入

4 4

.#.C

.#.#

....

S...



样例输出

4



样例解释


数据范围

思路
这道题其实可以用 
$spfa$
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)
        
                    打赏