题解 TeleportationMaze(topcoder 735div2) 翻车记

时间限制: 1 Sec 内存限制: 128 MB

题目描述

有一个N*M的迷宫,每个格子是空地或者障碍,现在从一个起点出发,共有2中操作。
1、沿着上、下、左、右4个方向走到相邻的空地上,时间是1
2、沿着上下左右4个方向,跨越障碍,跳到最近的空地上,时间是2
问,从起点到终点最少的时间。如果不能到达输出-1

输入

多组数据,第一行一个整数T(1<=T<=10)
第一行两个整数N和M(1<=N,M<=50),表示地图的大小
接下来N行,每行M个字符,仅包含两种字符“.”和“#”,分别表示空地和障碍
接下来4个整数r1、c1、r2、c2,表示起点和终点的行列。
起点终点保证唯一,且都是空地。

输出

从起点到终点最少时间。

样例输入

样例输出

Solution&&翻车记

第一眼看到这道题感觉非常水啊,一个连边+dijkstra就解决问题了。。。
于是20分钟写完题就自信的交了。。。

然后就翻车了,时间超限90%???这怎么可能边最多也只有50*50*4条,dijkstra会炸???Impossible

带着满满的doubt and disappointed。我请来了hjf大佬与cxy大佬,发现我犯了两个智障错误

  • 连边的时候忘记了break。。。
  • 清空数组的时候head不能直接从1~tot清空,必须全部清空。。。

凉凉

真心祝愿其他OIER不要跟我犯一样的错误,特别是NOIP时。绝对不要对自己的代码太自信。。。

思路就不讲了,dijkstra模板题。。。
code:

1 thought on “题解 TeleportationMaze(topcoder 735div2) 翻车记”

发表评论