题目链接: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}。【入口在最右边一条边】