首页 > ACM题库 > HDU-杭电 > hdu 2496 Moveable maze待解决[解题报告]C++
2014
02-09

hdu 2496 Moveable maze待解决[解题报告]C++

Moveable maze

问题描述 :

After solving a difficult programming problem, you decide to take a break and play a puzzle game. After playing the game for a while, you decide to write a program to solve it for you.

The game is played on a grid with R rows and C columns. Each square of the grid contains a black dot in the centre and black lines in the direction of some, none, or all of its north, east, south, and west neighbouring squares. Your objective in this game is to move your playing piece from the centre of the square in the i1th row and the j1th column, where it begins, to the centre of the square in the the i2th row and the j2th column.

You wish to do this in the least number of turns possible, where a turn consists of the following two parts. First in each turn, you may opt to select any grid square and rotate it 90 degrees clockwise or counterclockwise. Second in each turn, you may opt to move your piece from the centre of its current grid square to the centre of a neighbouring grid square, provided your piece does not leave the black markings. In other words, you may move from a square A to a neighbouring square B if A has a black line in the direction of B and B has a black line in the direction of A. Note that either part of a turn may be omitted.

输入:

Input consists of a number of test cases. The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R, C <= 20.

The next line contains the integers i1, j1, i2, j2, separated by spaces, with 1 <= i1, i2 <= R and 1 <= j1, j2 <= C.

The following R lines of input each contain one row of the grid, from north to south. Each of these lines contains exactly C strings of letters, separated by spaces, that correspond to squares of the grid, from west to east. Their format is as follows:

  • If the string is the single character x, then the square does not contain a line to any of its neighbours.
  • Otherwise, the string contains some of the characters N, E, S, W, which indicate that a black line extends from this square’s centre in the direction of its north, east, south, or west neighbour, respectively. No character will appear in the string more than once.

It is guaranteed that it is possible to move your playing piece from (i1, j1) to (i2, j2).

Input is terminated by a line containing 0 0. These zeros are not a test case and should not be processed.

输出:

Input consists of a number of test cases. The first line of each test case contains the two integers R and C, separated by spaces, with 1 <= R, C <= 20.

The next line contains the integers i1, j1, i2, j2, separated by spaces, with 1 <= i1, i2 <= R and 1 <= j1, j2 <= C.

The following R lines of input each contain one row of the grid, from north to south. Each of these lines contains exactly C strings of letters, separated by spaces, that correspond to squares of the grid, from west to east. Their format is as follows:

  • If the string is the single character x, then the square does not contain a line to any of its neighbours.
  • Otherwise, the string contains some of the characters N, E, S, W, which indicate that a black line extends from this square’s centre in the direction of its north, east, south, or west neighbour, respectively. No character will appear in the string more than once.

It is guaranteed that it is possible to move your playing piece from (i1, j1) to (i2, j2).

Input is terminated by a line containing 0 0. These zeros are not a test case and should not be processed.

样例输入:

4 2
1 1 4 1
E SW
x EW
NW ES
N x
0 0

Hint
A diagram of the input:

样例输出:

5

Hint
An example optimal solution is: 1. Rotate (2,2) clockwise. Step to (1,2). 2. Rotate (3,2) counterclockwise. Step to (2,2). 3. Rotate (3,2) counterclockwise. Step to (3,2). 4. Rotate (3,1) clockwise. Step to (3,1). 5. Rotate (3,1) clockwise. Step to (4,1).


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢