当前位置: 代码迷 >> 综合 >> POJ 3083 Children of the Candy Corn(走迷宫)
  详细解决方案

POJ 3083 Children of the Candy Corn(走迷宫)

热度:25   发布时间:2023-12-08 11:22:53.0

题目链接:POJ 3083

题意:

给一个迷宫,‘#’代表墙,'.'代表可行,’S‘代表入口,’E‘代表出口。分别求出:

①按左、上、右、下顺序前行从入口到出口的步数。

②按右、上、左、下顺序前行从入口到出口的步数。

③从入口到出口的最短步数。

入口在边上但不在拐角处。入口和出口也各算一步。

分析:

最短路径直接用BFS求解。

先分析第一种要求,即左上右下的顺序,第二种与之类似。

入口在不同的边上下一步走的方向下标变化是不一样的。

①当srow=0时,顺序是:   { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 };【入口在最上面一条边】
②当srow=h-1时,顺序是:{ 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 };【入口在最下面一条边】
③当scol=0时,顺序是:     { -1,0 },{ 0,1},{ 1,0 },{ 0,-1 };【入口在最左面一条边】
④当scol=w-1时,顺序是: { 1,0 },{ 0,-1 }, { -1,0 },{ 0,1}。【入口在最右边一条边】