首页 > 搜索 > BFS搜索 > hdu 2216 Game III-BFS-[解题报告]C++
2014
01-04

hdu 2216 Game III-BFS-[解题报告]C++

Game III

问题描述 :

Zjt and Sara will take part in a game, named Game III. Zjt and Sara will be in a maze, and Zjt must find Sara. There are some strang rules in this maze. If Zjt move a step, Sara will move a step in opposite direction.
Now give you the map , you shold find out the minimum steps, Zjt have to move. We say Zjt meet Sara, if they are in the same position or they are adjacent .
Zjt can only move to a empty position int four diraction (up, left, right, down). At the same time, Sara will move to a position in opposite direction, if there is empty. Otherwise , she will not move to any position.
The map is a N*M two-dimensional array. The position Zjt stays now is marked Z, and the position, where Sara stays, is marked E.

>  . : empty position
>  X: the wall
>  Z: the position Zjt now stay
>  S: the position Sara now stay

Your task is to find out the minimum steps they meet each other.

输入:

The input contains several test cases. Each test case starts with a line contains three number N ,M (2<= N <= 20, 2 <= M <= 20 ) indicate the size of the map. Then N lines follows, each line contains M character. A Z and a S will be in the map as the discription above.

输出:

The input contains several test cases. Each test case starts with a line contains three number N ,M (2<= N <= 20, 2 <= M <= 20 ) indicate the size of the map. Then N lines follows, each line contains M character. A Z and a S will be in the map as the discription above.

样例输入:

4 4
XXXX
.Z..
.XS.
XXXX
4 4
XXXX
.Z..
.X.S
XXXX
4 4
XXXX
.ZX.
.XS.
XXXX

样例输出:

1
1
Bad Luck!

使用四维数组进行状态判重  注意要用scanf(“%s“)或者gets  用cin莫名其妙WA  我查了30分钟错都没查出 改一下就好了 FUCK~~~

 

这道DK有更有效率的BFS 所以这次2个代码都贴上 任君瞻仰

 

 

 

 

 

 

解题转自:http://www.cnblogs.com/zhuangli/archive/2008/09/06/1285767.html


,
  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks