題目大意： 說有一個迷宮，迷宮有一個入口S和出口E，現在要你求出三種路徑各自的長度
1. 沿著最左邊走。
2. 沿著最右邊走。
3. 最短路徑。
其實沿著最左，最右方向走的時候，特別需要小心的是考慮在順時針和逆時針轉的時候，當前方向，選擇下一個位置，和下一個方向之間的關系。
為了更好的解釋，我用圖說明一下：
1. 沿著最左邊走：
當沿著最左邊緣的牆壁行走的時候，每次搜索的方向都是從當前方向的左邊，然後按照逆時針的方向進行搜索的。
不妨我們將搜索的四個點用數組表示 SearchDirection: (0, -1), (1,0), (0, 1), (-1, 0).
假如當前遍歷的 點是(r,c).
假設當前行走方向是 UP，那麼對應最左是 SearchDirection[0], 按照合法性搜索 0， 1， 2， 3；
如果當前行走方向是RIGHT， 那麼最左是SearchDirection[1], 合法搜索方向是 1, 2, 3, 0.
DOWN, SearchDirection[2], 2, 3, 1, 0
LEFT SearchDirection[3], 3, 0, 1, 2
根據初始方向容易決定搜索方向和搜索起始點，但是如何決定搜索以後的下一個方向呢。
如果當前選擇了, SearchDirection[0] -> 則對應最後的LEFT
SearchDirection[1] -> UP
SearchDirection[2] -> RIGHT
SearchDirection[3] -> DOWN
假設初始方向是 enum {UP, RIGHT, DOWN, LEFT} 表示的 d, 選擇的searchDirection是 i，那麼最後的方向就是 dNew = i + 3;
對於逆時針有類似的屬性。
關於最短路徑這裡，也有一些想法吧，最開始用DFS做了一下，發現結果超時了。
後來用BFS做了一下，就AC了。
其實做了幾個題目以後，個人感覺可達性問題是比較適合用DFS解決的，而最短路徑就比較適合用BFS解決。
提到最短路徑就時常會想起 Dijkstra，這個算法是解決單源最短路徑的經典算法，不過它針對的是更通用的問題，就是說每個邊的權重是一個整數，並且沒有負數環。
而這裡問題是很簡單的，根據兩點的拓撲可達性，距離只有0 和 1，所以利用BFS解決是更合理的方法。
在DFS中，回溯過程會所搜索很多空間，並不適合求最短路徑。而BFS因為在求解的過程中，將遍歷的過的節點不再繼續遍歷，所以會有比較高的效率。
代碼如下：
[cpp]
#include <stdio.h>
#include <memory.h>
#define MAX_GRID 45
struct Grid
{
int r;
int c;
int nSteps;
Grid(int _r, int _c)
{
r = _r;
c = _c;
nSteps = 0;
}
Grid()
{
nSteps = 0;
}
};
bool operator == (const Grid&a, const Grid &b)
{
return a.r == b.r && a.c == b.c;
}
bool operator != (const Grid &a,const Grid&b)
{
return (a.r != b.r) || (a.c != b.c);
}
Grid g_Neighbors[4] =
{ Grid(0, -1), Grid(-1,0), Grid(0, 1), Grid(1, 0)
};
enum Direction{UP = 0, RIGHT, DOWN, LEFT};
int g_Yard[MAX_GRID][MAX_GRID];
int nCol, nRow;
Grid GetNewPoint(const Grid ¤tGrid, int iNeighbor)
{
Grid g = Grid(currentGrid.r + g_Neighbors[iNeighbor].r, currentGrid.c + g_Neighbors[iNeighbor].c);
return g;
}
void GetLeftMost(const Grid ¤tGrid, Direction d, Grid &nextGrid, Direction &nextdirection )
{
int iStart = (int)d;
Grid g;
for( int i = 0; i < 4; i++)
{
g = GetNewPoint(currentGrid, (iStart + i)%4);
if(g_Yard[g.r][g.c] == 1)
{
continue;
}
else
{
nextGrid = g;
nextdirection = Direction(((int)d + i + 3)%4);
break;
}
}
}
void GetRightMost(const Grid ¤tGrid, Direction d, Grid &nextGrid, Direction &nextdirection)
{
int iStart = ((int)d + 2)%4;
Grid g;
for( int i = 4; i > 0; i--)
{
g = GetNewPoint(currentGrid, (iStart + i)%4);
if(g_Yard[g.r][g.c] == 1)
{
continue;
}
else
{
nextGrid = g;
nextdirection = Direction(((int)d + i + 1)%4);
break;
}
}
}
Direction GetInitialDirection(const Grid &start)
{
if(start.r == 0)
{
return DOWN;
}
if(start.r == nRow - 1)
{
return UP;
}
if(start.c == 0)
{
return RIGHT;
}
if(start.c == nCol - 1)
{
return LEFT;
}
}
int findStepsForLeftmost(const Grid &start, const Grid &exit)
{
Direction d = GetInitialDirection(start);
int nSteps = 1;
Grid currentGrid = start, nextGrid;
while( currentGrid != exit)
{
GetLeftMost(currentGrid, d,nextGrid, d);
currentGrid = nextGrid;
nSteps ++;
}
return nSteps;
}
int findStepsForRightmost(const Grid &start, const Grid &exit)
{
Direction d = GetInitialDirection(start);
int nSteps = 1;
Grid currentGrid = start, nextGrid;
while( currentGrid != exit)
{
GetRightMost(currentGrid, d,nextGrid, d);
currentGrid = nextGrid;
nSteps ++;
}
return nSteps;
}
Grid q[2000];
bool GridLegal(const Grid &g)
{
if( g.r < 0 || g.r >= nRow || g.c < 0 || g.c >= nCol || g_Yard[g.r][g.c] == 1)
{
return false;
}
return true;
}
int BFS(const Grid &start, const Grid & exit)
{
int front, rear;
front = rear = 0;
q[rear++] = start;
while(rear > front)
{
Grid top = q[front];
if(top == exit)
{
return top.nSteps;
}
//iterate the neighboring
for(int i = 0; i < 4; i++)
{
Grid neighbor = GetNewPoint(top, i);
if(GridLegal(neighbor))// not visited
{
g_Yard[neighbor.r][neighbor.c] = 1;
neighbor.nSteps = top.nSteps + 1;
q[rear++] = neighbor;
}
}
front++;
}
return -1;
}
int main()
{
int nCase;
scanf("%d", &nCase);
while(nCase--)
{
scanf("%d%d", &nCol, &nRow);
int i,j;
char c;
memset(g_Yard, 0, sizeof(g_Yard));
Grid start, exit;
for( i = 0; i < nRow; i++)
{
getchar();
for( j = 0; j < nCol; j++)
{
c = getchar();
if( c == '#')
{
g_Yard[i][j] = 1;
}
else if( c == 'S')
{
start.r = i;
start.c = j;
g_Yard[i][j] = 1;
}
else if( c == 'E')
{
exit.r = i;
exit.c = j;
}
}
}
int minSteps = 10000000;
int leftmost = findStepsForLeftmost(start, exit);
int rightmost = findStepsForRightmost(start, exit);
minSteps = BFS(start, exit);
printf("%d %d %d\n",leftmost ,rightmost, minSteps+1);
}
return 0;
}
