注：搬運自我的csdn博客 http://blog.csdn.net/qq_30172585
題意重述
一個迷宮抡四，從起點走到終點，走一步有直走仗谆，以及直走再右轉(zhuǎn)兩個選擇（注意不能原地轉(zhuǎn)彎）指巡，問在這種情況下的最短路徑是多少，起始方向可以任意選擇隶垮，題目中保證這樣的路徑一定存在
題目分析與算法選擇
既然要搜索最短的路徑藻雪，那就是用的bfs了，因為這里狀態(tài)每深入一層狸吞，路徑就增加固定的值1勉耀，因此對狀態(tài)由淺到深搜索指煎，得出的就是最短的路徑。
具體實現(xiàn)
狀態(tài)的確定
首先，在網(wǎng)格地圖里移動，狀態(tài)肯定包括所在點的坐標镰官，而且由于“Right Head”的下一步走法與當前的方向相關(guān)，所以方向也是狀態(tài)的一個成員崇渗。同時，用一個數(shù)組steps來儲存初始狀態(tài)到當前狀態(tài)的路徑長京郑，當狀態(tài)向下深入一層時宅广，就把深層的狀態(tài)的steps值設(shè)置為上一層的steps加一。這樣當找到終點時些举，當時狀態(tài)的steps值就是初始狀態(tài)到終點的最短路徑
剪枝
如果不進行剪枝跟狱，直接最原始的廣搜的話，會產(chǎn)生很多沒有用的搜索過程户魏，例如下圖中從最初狀態(tài)分出兩條路線驶臊，分別是綠色路線和藍色路線。藍色路線在第二層（箭頭數(shù)字2）中產(chǎn)生了一個位置在（3,1）叼丑，方向向左的狀態(tài)关翎；而綠色路線在第四層（箭頭數(shù)字4）中同樣產(chǎn)生了一個位置在（3,1），方向向左的狀態(tài)鸠信，很明顯藍色路線在該處產(chǎn)生的狀態(tài)的路徑比綠色路徑在此產(chǎn)生的狀態(tài)的路徑短（2 < 4）纵寝，因此綠色路徑的狀態(tài)（3，1星立，左）不應該再向下搜索爽茴。
代碼如下：
#include<stack>
#include<iostream>
#include<fstream>
#include<cmath>
#include<string>
#include<cstdio>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;
struct status {
int x;
int y;
int dir;
status(int _x, int _y, int _dir)
{
x = _x, y = _y, dir = _dir;
}
};
char maze[21][21];
int directions[4][2] = { {-1,0},{0,1},{ 1,0 },{ 0,-1 } };//up, right, down, left
int steps[21][21][21];
queue<status> que;
int test;
int* dir2pair(int dir)//0 for up, 1 for right, 2 for down, 3 for left
{
dir = dir % 4;
return directions[dir];
}
int dfs(int x, int y, int dir)
{
memset(steps, 1, sizeof(steps));//steps[][][] = 16843009 = (2進制)00000001 00000001 00000001 00000001
steps[x][y][dir] = 0;
status sta = status(x, y, dir);
que.push(sta);
while (!que.empty())
{
status s = que.front(); que.pop();
int x = s.x; int y = s.y; int dir = s.dir;
for (int d = dir; d <= dir + 1; d++)
{
int dir_real = d % 4;
int* dirpair = dir2pair(dir_real);
int next_x = x + dirpair[0]; int next_y = y + dirpair[1];
if (maze[next_x][next_y] == 'F')
return steps[x][y][dir] + 1;
//steps[next_x][next_y][dir_real] > steps[x][y][dir] + 1 在此之前沒有出現(xiàn)更少的步數(shù)，才能更新绰垂。 這句用來剪枝
if (maze[next_x][next_y] != 'X' && steps[next_x][next_y][dir_real] > steps[x][y][dir] + 1)
{
steps[next_x][next_y][dir_real] = steps[x][y][dir] + 1;
status sta = status(next_x,next_y,dir_real);
que.push(sta);
}
}
}
return 9999999;
}
int main()
{
int n, r, c;
cin >> n;
int sx, sy, fx, fy;
while (n--)
{
while (!que.empty())
que.pop();
cin >> r >> c;
for (int i = 0; i < r; i++)
{
getchar(); //將換行符讀掉
for (int k = 0; k < c; k++)
{
cin.get(maze[i][k]); //get方法能讀取空格
if (maze[i][k] == 'S')
sx = i, sy = k;
else if (maze[i][k] == 'F')
fx = i, fy = k;
}
}
int min_res = 99999999;
for (int i = 0; i < 4; i++)
{
int res = dfs(sx, sy, i);
min_res = min_res < res ? min_res : res;
}
cout << min_res << endl;
}
}
