/******************************************************************************
??????????????????????????分支限界--走迷宮問題?
*******************************************************************************/
/*
*問題描述：一個網(wǎng)格迷宮由n行m列的單元格組成，每個單元格要么是空地（用1表示），
*??????????要么是障礙物（用0?表示）。找出從起點到終點的最短移動序列，其中UDLR
*??????????分別代表往上，下，左，右移動到相鄰單元格。任何時候都不能在障礙格中，
*??????????也不能走到迷宮之外，起點和終點保證是空地。nm<=100.
*?
*分析：????可以使用bfs，節(jié)點的訪問順序恰好是它們從根節(jié)點距離從小到大的順序。類
*??????????似的，也可以用bfs來按照起點的距離順序遍歷迷宮圖。不斷沿著父親指針走，
*??????????保存方向序列dir，最后反向輸出。
*??????????比深度優(yōu)化的效率要高很多，因為每次都定義了活結(jié)點還有下一個擴展節(jié)點，
*??????????在活結(jié)點當中去尋找擴展節(jié)點，不會盲目的搜索到底，而是有一定的選擇性。?
*??????????因此我們可以定義記錄擴展節(jié)點的數(shù)組，并且定義函數(shù)來判斷，看下一層將要
*??????????被搜索的節(jié)點是不是能夠作為擴展節(jié)點。這就運用到了分支限界的知識。
*?
*/

#include
#include
using?namespace?std;

#define?MAXN?1000
//int?dir[MAXN];?????//非遞歸顯示該迷宮遍歷格子的時候需要使用的寄存數(shù)組。?
int?q[MAXN*MAXN];????//該數(shù)組表示存放選入成為活結(jié)點的，節(jié)點的編號

int?n?=?6m?=?5;?????//定義一個具有六行五列的格子陣。n是表示行數(shù)量，m表示列數(shù)量?

int?dx[4]={-1100};//行列變換數(shù)組，定義下標0123，分別代表上下左右，
?????????????????????//dx代表行號通過上下左右進行的變換，?因此dx[0]=-1表示向上
?????????????????????//移動行號變?yōu)?1，dx[1]=1表示向下移動行號+1，
?????????????????????//表示dx[2]=0dx[3]=0?左右行號不變?
?????????????????????
int?dy[4]={00-11};//定義下標0123，分別代表上下左右，
?????????????????????//因此在上下的時候列號不變，左右的時候列號-1，+1.?
?????????????????????
int?fa[6][5];???????//?保存新格子的父親編號。?
int?last_dir[6][5];?//記錄上下左右的數(shù)組，其數(shù)值只能為0123?。存放的是之前的
????????????????????//格子到當前格子所需要前進的方向。0123，分別代表上下左右?
????????????????????
int?dist[6][5];?????//保存，擴展到該節(jié)點所用的步數(shù)?

int?vis[6][5];??????//只存兩個數(shù)0和1。并且1表示格子滿0表示格子空?
?
char?name[10];??????//打印移動方向的時候所對應(yīng)的方向名字。?
?

void?bfs（int?x?int?y）
{
?????int?front?=?0??rear?=?0??du;
?????
?????u=x*m+y;??????????//x表示行號，y表示列號u表示編號。
?????vis[x][y]=1;??????//vis記錄格子（xy）是否被走過。1表示格子滿，0表示格子空。
?????fa[x][y]?=?u;?????//保存新格子的父親編號，以便打印的時候遍歷所有的格子。?
?????dist[x][y]=0;?????//保存，起點擴展到該節(jié)點所用的步數(shù)為0?
?????q[rear++]?=?u?;???//存放活節(jié)點對應(yīng)的編號。
??????
?????while（front?????????????????????????//及rear=front的時候退出循環(huán)?
?????{
???????u=q[front++];????//取出活結(jié)點當中的首元素作為擴展節(jié)點，?
???????x?=?u/m;?y?=?u%m;
???????for（d=0;d<4;d++）?//遍歷四個方向?
???????{
??????????int?nx?=?x?+?dx[d]ny?=?y+dy[d];//算出新的行坐標與列坐標?
??????????
??????????if（nx>=0&&nx=0&&ny??????????{
????????????int?v?=?nx*m+ny;?????????????//算出新的數(shù)字編號?
????????????q[rear++]?=?v;???????????????//將該活節(jié)點的編號放入到活結(jié)點的隊列里。?
????????????vi