平顶山学院16-17学年第一学期第一次排名赛

  • 内容
  • 评论
  • 相关

比赛名称:平顶山学院16-17年第一学期第一次排名赛

参赛人员:          ACM算法公关部全体成员        

    出 题 人:              黄    峥 陶林娟               

比赛时间: 2016年11月10日19:00-11月20日19:00

归档时间:             2016年11月29日           

  • 题目描述   

题目名称:A计划

题目来源:HDOJ

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来拯救公主。不过公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。

现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用*表示,平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死。骑士们在一层中只能前后左右移动,每移动一格花1时刻。层间的移动只能通过时空传输机,且不需要任何时间。

输入

输入的第一行C表示共有C个测试数据,每个测试数据的前一行有三个整数N,M,T。 N,M迷宫的大小N*M(1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况,后N*M表示迷宫第二层的布置情况。

输出

如果骑士们能够在T时刻能找到公主就输出“YES”,否则输出“NO”。

样例输入

1

5 5 14

S*#*.

.#...

.....

****.

...#.

 

..*.P

#.*..

***..

...*.

*.#..

样例输出

YES

  • 考核知识点

搜索。

  • 常见误区

有些人会出现思路错误,会想先判断公主在第几层,如果在第一层,只用传统广搜,如果在第二层在考虑坐传送机过去,然而这种思路是错误的,因为迷宫有两层,路的情况是不一样的,不能这样片面的去考虑。

  • 解题思路

这个题目与平时做的搜索题目不同的是,平常做的广搜迷宫是二维的,而现在是一个两层的迷宫,其实就是三维的迷宫,迷宫中比较特别的有传送机,只有遇到传送机了,才能被传送到另一层。因此对于特殊的情况,我们采取特殊的处理和考虑,对于普通情况则直接按传统的广搜进行处理。根据题意,特殊情况有下面几种。

  1. 如果走到某位置是’#’,代表是传送门,如果对面是墙,那么过去就会被撞死,那么这个位置是不能走的。
  2. 还是走到某个位置是’#’代表传送门,如果对面也是传送门,那么勇士将在两层迷宫件无线传输下去,这样它也救不出公主。
  3. 其余情况均按传统广搜处理。

具体思路:采用队列。

数据结构的定义:

struct pos

{

int x;//走到某点的横坐标

int y;//走到某一点的纵坐标

int step;//从起点走到某一个地方所用的时间。

}

搜索方向可以规定为上、右、下、左(这里不做要求,按每个人的习惯定义搜索顺序即可),定义pos cur,nex,cur为前一位置,nex为下一位置。如果nex位置没有出界,不是墙,而且没有访问过,那么讨论这一点的情况,如果是空地,则按传统广搜处理,标记这一点,然后入队,如果是公主所在的位置,就看当前时间是否大于规定救出公主所用的最大时间,如果大于了,则说明救不出公主,否则公主得救,如果这一点为传送门,如果对面为墙,传送门或已经访问过,则说明当前这个地方不能走,否则通过传送门走到对面。

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :141210133  胡晓康

    院系 :计算机学院(软件学院)

    专业班级: 14计科1班

 

 

 

 

  • 题目描述

题目名称:Number Sequence

题目来源:HDOJ

Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

输入

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].

输出

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

样例输入

2

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2

1 2 3 1 3

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2

1 2 3 2 1

样例输出

6

-1

  • 考核知识点

kmp算法知识

  • 常见误区

用朴素法(暴力)BF算法求解导致时间超限!

  • 解题思路
  • kmp算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。1.
  • o7yidnmmd4afx3l
  • 首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。
  • 2.
  • ddu8odww9jto33lyx7
  • 因为B与A不匹配,搜索词再往后移。3.
  • lbikr_f8snt5ke8gbuc
  • 就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。4.
  • d48nvk6q8bbojrgdnfj接着比较字符串和搜索词的下一个字符,还是相同。5.
  • qdg3ipz1ug_gnews3b_i
  • 直到字符串有一个字符,与搜索词对应的字符不相同为止。6.
  • lhchia1yxtsqujmdk这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。7.
  • nkqnsbj5n%30rf7gllwpa一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。8.
  • obcytq6vnuhw_v1m9rxt怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。9.
  • enhjrbxg2_73ixo6ys已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:移动位数 = 已匹配的字符数 - 对应的部分匹配值

    因为 6 - 2 等于4,所以将搜索词向后移动4位。

    10.

  • o_ozuh8_4gn4bw3dp
  • 因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。11.
  • 3vaj_tufba1sajs_vl3因为空格与A不匹配,继续后移一位。 

     

    12

    .we7jwjx46z5t_g

    逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。

    13.

  • brnvhb_fhmhqskosufy逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。14.
  • 8qxnws9z73ox2_p5ubmd7下面介绍《部分匹配表》是如何产生的。首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

    15.

  • 06l6rs2yi0t8ob"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,- "A"的前缀和后缀都为空集,共有元素的长度为0;

    - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

    - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

    - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

    - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;

    - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;

    - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

    16

    .5f679_eml8oszoj%fc8ioe

    "部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :141210118  王成

    院系 :计算机学院(软件学院)

    专业班级: 14计科1班

 

 

 

 

  • 题目描述

题目名称诡异的楼梯

题目来源:HDOJ

Hogwarts正式开学以后,Harry发现在Hogwarts里,某些楼梯并不是静止不动的,相反,他们每隔一分钟就变动一次方向.
比如下面的例子里,一开始楼梯在竖直方向,一分钟以后它移动到了水平方向,再过一分钟它又回到了竖直方向.Harry发现对他来说很难找到能使得他最快到达目的地的路线,这时Ron(Harry最好的朋友)告诉Harry正好有一个魔法道具可以帮助他寻找这样的路线,而那个魔法道具上的咒语,正是由你纂写的.

输入

测试数据有多组,每组的表述如下:第一行有两个数,M和N,接下来是一个M行N列的地图,'*'表示障碍物,'.'表示走廊,'|'或者'-'表示一个楼梯,并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向,'-'表示的楼梯在一开始是水平方向.地图中还有一个'S'是起点,'T'是目标,0<=M,N<=20,地图中不会出现两个相连的梯子.Harry每秒只能停留在'.'或'S'和'T'所标记的格子内.

输出

只有一行,包含一个数T,表示到达目标的最短时间.
注意:Harry只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且Harry登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,Harry从来不在楼梯上停留.并且每次楼梯都恰好在Harry移动完毕以后才改变方向.

样例输入

5 5

**..T

**.*.

..|..

.*.*.

S....

    样例输出

7

  • 考核知识点

广搜

  • 常见误区

楼梯每走一步都在变化,并且跨过的楼梯也不能为墙或者越界

  • 解题思路

该题目用到广搜,在走的过程分上下、左右两种。

上下两个方向走,如果走的地方不是墙,上下走遇到竖着的楼梯对面不是墙并且不越界,可以走过去,如果遇见横着的楼梯并且对面不是墙并且不越界等一秒再过去,其他情况直接走。

反之左右走,如果走的地方不是墙,左右走遇到横着的楼梯对面不是墙并且不越界,可以走过去,如果遇见竖着的楼梯并且对面不是墙并且不越界等一秒再过去,其他情况直接走。

最后找到终点并输出时间。

  • 参考答案(附关键注释)

  • 整理者

    学号姓名 :151210118 黄峥

    院系 :计算机学院(软件学院)

    专业班级: 15计科1班

 

 

 

 

 

  • 题目描述

题目名称:Tempter of the Bone

题目来源:HDOJ

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

输入

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.

输出

For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.

   样例输入

4 4 5

S.X.

..X.

..XD

....

3 4 5

S.X.

..X.

...D

0 0 0

样例输出

NO

YES

  • 考核知识点

广搜的一个简单应用,但是这道题在考察广搜的基础上还应用到了剪枝的思想来优化代码。

补充下奇偶剪枝 把矩阵看成如下形式:

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0 0

1 0 1 0 1

从为 0 的格子走一步,必然走向为 1 的格子 。

从为 1 的格子走一步,必然走向为 0 的格子 。

即: 从 0 走向 1 必然是奇数步,从 0 走向 0 必然是偶数步。

所以当遇到从 0 走向 0 但是要求时间是奇数的或者 从 1 走向 0 但是要求时间是偶数的,都可以直接判断不可达!比如有一地图

S...

....

....

....

...D

要求从S点到达D点,此时,从S到D的最短距离为s = abs ( dx - sx ) + abs ( dy - sy )。如果地图中出现了不能经过的障碍物:

S..X

XX.X

...X

.XXX

...D

此时的最短距离s' = s + 4,为了绕开障碍,不管偏移几个点,偏移的距离都是最短距离s加上一个偶数距离。就如同上面说的矩阵,要求你从0走到0,无论你怎么绕,永远都是最短距离(偶数步)加上某个偶数步;要求你从1走到0,永远只能是最短距离(奇数步)加上某个偶数步。

也就是说所要求的时间为t的话,起始点(sx,sy),终点(ex,ey)如果

t-[abs(ex-sx)+abs(ey-sy)] 结果为偶数,则可以在t步恰好到达;这是奇偶剪枝的主要应用。

 

  • 常见误区

没有应用到奇偶剪枝的思想,导致超限。

  • 解题思路

迷宫中有一个出口,但是这个出口的门在最开始的时候是关着的,要求小狗必须在题目要求的第T秒到达这个出口的位置,此时这个门刚好打开且时间小于一秒,小狗刚好能出去。小狗只能够在上下左右移动,每当小狗到达一个位置的时候,这个地方地面就开始下沉并在下一秒消失。

在考虑走的情况的时候,值得注意的是题目上对于出去迷宫的时间的要求,必须在第T秒而不是在T秒内。

  • 参考答案(附关键注释)

  • 整理者

学号姓名 :151210114 崔梦梦

院系 :计算机学院(软件学院)

专业班级: 15计科1班

 

 

 

 

 

  • 题目描述

题目名称:N皇后问题

题目来源:HDOJ

N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。 你的任务是,对于给定的N,求出有多少种合法的放置方法。

输入

共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。

输出

共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。

样例输入

1

8

5

0

样例输出

1

92

10

  • 考核知识点

深度优先搜索(DFS)

  • 常见误区
  1. 没有打表导致提交时时间超限。
  2. 在判断什么时候需要进行递归,什么时候直接进行下一步的判断条件没有控制好。
  • 解题思路

要解决N皇后问题,其实就是要解决好怎么放置这n个皇后,每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线,在这里我们可以以行优先,就是说皇后的行号按顺序递增,只考虑第i个皇后放置在第i行的哪一列,所以在放置第i个皇后的时候,可以从第1列判断起,如果可以放置在第1个位置,则跳到下一行放置下一个皇后。如果不能,则跳到下一列...直到最后一列,如果最后一列也不能放置,则说明此时放置方法出错,则回到上一个皇后向之前放置的下一列重新放置。此即是递归法的精髓所在。当第n个皇后放置成功后,即得到一个可行解,此时再回到上一个皇后重新放置寻找下一个可行解...如此后,即可找出一个n皇后问题的所有可行解。

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210220  胡娇

    院系 :计算机学院(软件学院)

    专业班级: 15计科2班

 

 

 

 

 

 

  • 题目描述

题目名称:逃离迷宫

题目来源:HDOJ

给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的4个位置中,当然在行走过程中,gloria不能走到迷宫外面去。令人头痛的是,gloria是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。我们假定给定的两个位置都是空地,初始时,gloria所面向的方向未定,她可以选择4个方向的任何一个出发,而不算成一次转弯。gloria能从一个位置走到另外一个位置吗?

输入 

第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数,接下来为t组测试数据,每组测试数据中,   第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数,接下来m行,每行包括n个字符,其中字符'.'表示该位置为空地,字符'*'表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为5个整数k, x[sub]1[/sub], y[sub]1[/sub], x[sub]2[/sub], y[sub]2[/sub] (1 ≤ k ≤ 10, 1 ≤ x[sub]1[/sub], x[sub]2[/sub] ≤ n, 1 ≤ y[sub]1[/sub], y[sub]2[/sub] ≤ m),其中k表示gloria最多能转的弯数,(x[sub]1[/sub], y[sub]1[/sub]), (x[sub]2[/sub], y[sub]2[/sub])表示两个位置,其中x[sub]1[/sub],x[sub]2[/sub]对应列,y[sub]1[/sub], y[sub]2[/sub]对应行。

输出

每组测试数据对应为一行,若gloria能从一个位置走到另外一个位置,输出“yes”,否则输出“no”。

样例输入 

2

5 5

...**

*.**.

.....

.....

*....

1 1 1 1 3

5 5

...**

*.**.

.....

.....

*....

2 1 1 1 3

样例输出

no

yes

 

  • 考核知识点

广搜

  • 常见误区

输入是的横纵坐标弄反了,还有步数一开始不要定义为0,要不然在从定点出发之后,他就会+1,另外就是从一个方向一搜到底!

  • 解题思路

输入的话,输入地图的时候是按行读取到二维数组里面的。另外就是,题目是先输入列后输入行,要注意。之后就是进行bfs.每走一个点,这个点都应该包括三个数据,横纵坐标还有在当前定点的时候的拐弯次数。我们要设当前所占的点为定点,然后向四个方向去扩展,也就是BFS,但是这里要注意的是,它的扩展是按照一个方向一次性搜到这个方向的底部直到不能继续在搜索,然后再搜另外几个方向。因为题目当中有着拐弯次数这样的一个限制条件。搜索的时候,顶点的顺序是按照,拐弯次数为0,为1,这样以此类推的顺序向下搜索的。因为从起点开始,我们设起点的拐弯次数为-1.因为从起点走到下一个扩展点是不需要转弯的,这一点是题目的限制条件。我们走的之后,每一次肯定要先走拐弯次数为0的,然后再走为1,为2的,这也就造成了顶点入队列的时候的顺序有所不同。假设我现在从起点出来,所有拐弯次数为0的顶点都已经入队列,然后弹出一个,再进行四个方向的扩展搜索把拐弯次数为1的部分顶点入队列。如果四个方向搜完之后都没搜到答案,那么再从队列头部弹出一个拐弯次数为0的点进行搜索,这样,能保证搜到正确答案的时候,走的路径也是最短的。

  • 参考答案(附关键注释)

  • 整理者

学号姓名 :151210209  赵永旗

院系 :计算机学院(软件学院)

专业班级:15计科2班

 

 

 

 

 

 

  • 题目描述

题目名称:Ignatius and the Princess I

题目来源:HDOJ

The Princess has been abducted by the BEelzebub feng5166, our hero Ignatius has to rescue our pretty Princess. Now he gets into feng5166's castle. The castle is a large labyrinth. To make the problem simply, we assume the labyrinth is a N*M two-dimensional array which left-top corner is (0,0) and right-bottom corner is (N-1,M-1). Ignatius enters at (0,0), and the door to feng5166's room is at (N-1,M-1), that is our target. There are some monsters in the castle, if Ignatius meet them, he has to kill them. Here is some rules:

 

1.Ignatius can only move in four directions(up, down, left, right), one step per second. A step is defined as follow: if current position is (x,y), after a step, Ignatius can only stand on (x-1,y), (x+1,y), (x,y-1) or (x,y+1).

2.The array is marked with some characters and numbers. We define them like this:

. : The place where Ignatius can walk on.

X : The place is a trap, Ignatius should not walk on it.

n : Here is a monster with n HP(1<=n<=9), if Ignatius walk on it, it takes him n seconds to kill the monster.

 

Your task is to give out the path which costs minimum seconds for Ignatius to reach target position. You may assume that the start position and the target position will never be a trap, and there will never be a monster at the start position.

输入

The input contains several test cases. Each test case starts with a line contains two numbers N and M(2<=N<=100,2<=M<=100) which indicate the size of the labyrinth. Then a N*M two-dimensional array follows, which describe the whole labyrinth. The input is terminated by the end of file. More details in the Sample Input.

输出

For each test case, you should output "God please help our poor hero." if Ignatius can't reach the target position, or you should output "It takes n seconds to reach the target position, let me show you the way."(n is the minimum seconds), and tell our hero the whole path. Output a line contains "FINISH" after each test case. If there are more than one path, any one is OK in this problem. More details in the Sample Output.

样例输入

5 6

.XX.1.

..X.2.

2...X.

...XX.

XXXXX.

5 6

.XX.1.

..X.2.

2...X.

...XX.

XXXXX1

5 6

.XX...

..XX1.

2...X.

...XX.

XXXXX.

样例输出

It takes 13 seconds to reach the target position, let me show you the way.

1s:(0,0)->(1,0)

2s:(1,0)->(1,1)

3s:(1,1)->(2,1)

4s:(2,1)->(2,2)

5s:(2,2)->(2,3)

6s:(2,3)->(1,3)

7s:(1,3)->(1,4)

8s:FIGHT AT (1,4)

9s:FIGHT AT (1,4)

10s:(1,4)->(1,5)

11s:(1,5)->(2,5)

12s:(2,5)->(3,5)

13s:(3,5)->(4,5)

FINISH

It takes 14 seconds to reach the target position, let me show you the way.

1s:(0,0)->(1,0)

2s:(1,0)->(1,1)

3s:(1,1)->(2,1)

4s:(2,1)->(2,2)

5s:(2,2)->(2,3)

6s:(2,3)->(1,3)

7s:(1,3)->(1,4)

8s:FIGHT AT (1,4)

9s:FIGHT AT (1,4)

10s:(1,4)->(1,5)

11s:(1,5)->(2,5)

12s:(2,5)->(3,5)

13s:(3,5)->(4,5)

14s:FIGHT AT (4,5)

FINISH

God please help our poor hero.

FINISH

  • 考核知识点

广搜。

  • 常见误区

这个题目用广搜求解的时候,要使用优先队列,因为这个题目后入队的元素所对应的时间有可能比先入队的时间要小 。

  • 解题思路

首先翻译一下题目大意:国王被一个坏人抓走了,然后勇士要去就国王,坏人住的地方一个N*M的二维迷宫,坏人的房间在[N-1][M-1]位置上,勇士的起点只能是(0,0),勇士在迷宫中只能向四个方向每次走一步,即上、下、左、右四个方向。‘.’代表空地,勇士可以行走,‘X’代表陷阱,不可以行走,‘1’~‘9’代表这个位置有妖怪,打死这个妖怪需要这么多时间。题目指出,起点位置永远不可能有妖怪,要输出救到国王的最短时间,如果可以救到国王,还要输出对应的路径,如果不能救到国王,则输出题目要求输出的一句话。

具体解题思路:要用优先队列,因为如果勇士走到一个有妖怪的位置,那么要花费时间打死妖怪,这样的话就说明后入队的点所对应的时间可能比先入队的点所耗费的时间少,因此要使用优先队列,队列的优先级是所用时间少的先出队,这样的就能保证,如果救到了国王,那么所用的时间有一定是最少的,题目中说,如果耗时最少的路径有多条,只用输出其中的一条即可,如果用普通队列,或深搜,都会非常耗时。

具体数据结构的定义

struct pos

{

int x,y,time;///x,y为点的坐标,time为从起点走到该点所用的时间

string path;//path用来保存从起点走到(x,y)的路径

friend bool operator < (pos a,pos b)//运算符重载

{

return a.time > b.time;

}

}

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210107  温雅新

    院系 :计算机学院(软件学院)

    专业班级: 15计科1班

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注