迷宮問題——經典廣搜

廣度優先搜尋Breadth-First-Search，對于每個節點都優先将該節點的所有下一個節點搜尋一遍，再進入下一層搜尋。

廣度優先搜尋适用于尋找最短路徑問題，所有因為展開節點而得到的子節點都會被加進一個先進先出的隊列中。

廣搜模闆
BFS()
{
	初始化隊列；
	while(隊列不為空且未找到目标節點)
	{
		取隊首節點擴充，并将擴充出的節點放入隊尾；
		必要時要記住每個節點的父節點；
	}
}
           

bool BFS(Node& Vs, Node& Vd){  
    queue<Node> Q;  
    Node Vn, Vw;  
    int i;  
  
    //初始狀态将起點放進隊列Q  
    Q.push(Vs);  
    hash(Vw) = true;//設定節點已經通路過了！  
  
    while (!Q.empty()){//隊列不為空，繼續搜尋！  
        //取出隊列的頭Vn  
        Vn = Q.front();  
  
        //從隊列中移除  
        Q.pop();  
  
        while(Vw = Vn通過某規則能夠到達的節點){  
            if (Vw == Vd){//找到終點了！  
                //把路徑記錄，這裡沒給出解法  
                return true;//傳回  
            }  
  
            if (isValid(Vw) && !visit[Vw]){  
                //Vw是一個合法的節點并且為白色節點  
                Q.push(Vw);//加入隊列Q  
                hash(Vw) = true;//設定節點顔色  
            }  
        }  
    }  
    return false;//無解  
}  
           

或者是

void bfs(int x, int y, int m, int n) {  
    queHead = queTail = 0; // 清空隊列  
    // 将(x, y)加入隊列  
    que[queTail++] = Node(x, y);  
    vis[x][y] = true;  
    // 開始BFS搜尋  
    for (; queHead < queTail; ++queHead) {  
        // 探查隊首元素周圍的n個位置  
        for (int i = 0; i < n; ++i) {  
            // 根據偏移量計算位置  
            Node nxt(que[queHead].x + dx[i], que[queHead].y + dy[i]);  
            // 若該位置在地圖中且為未通路過的'@'，則加入隊列  
            if (滿足條件 && !vis[nxt.x][nxt.y] ) {  
                que[queTail++] = nxt;  
                vis[nxt.x][nxt.y] = true;  
            }  
        }  
    }  
}  
  
           

/*
迷宮問題
檢視 送出 統計 提問
總時間限制: 1000ms 記憶體限制: 65536kB
描述
定義一個二維數組： 

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一個迷宮，其中的1表示牆壁，0表示可以走的路，隻能橫着走或豎着走，不能斜着走，要求程式設計式找出從左上角到右下角的最短路線。



輸入
一個5 × 5的二維數組，表示一個迷宮。資料保證有唯一解。
輸出
左上角到右下角的最短路徑，格式如樣例所示。
樣例輸入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
樣例輸出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
----------------------------廣度搜尋------------------------------------------------
本題第一次做的時候，關鍵是父節點的記錄出現了問題
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
bool vis[5][5],board[5][5];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
struct Point
{
	int x,y,num;
	Point* father;
	Point(){};
	Point(int x_,int y_,int num_):x(x_),y(y_),num(num_){};
	bool right()
	{
		if(x >= 0 && x < 5 && y >= 0 && y < 5 && num == 0)
			return true;
		return false;
	}
};
void outPut(Point & a)
{
	if(a.x != 0 || a.y != 0)
	{
		outPut(*a.father);
		cout << "(" << a.x << "," << a.y << ")" << endl;
	}
	else
		cout << "(" << a.x << "," << a.y << ")" << endl;
}
void BFS(Point & a)
{
	queue<Point>  Q;
	Q.push(a);
	Point Pn;
	vis[a.x][a.y] = true;
	while(!Q.empty())
	{
		Pn = Q.front();
		Q.pop();
		for(int i = 0; i < 4; ++i)
		{
			Point Pw(Pn.x+dx[i],Pn.y+dy[i],board[Pn.x+dx[i]][Pn.y+dy[i]]);
			Pw.father = &Pn;
			if(Pw.right() && !vis[Pw.x][Pw.y])
			{
				if(Pw.x == 4 && Pw.y == 4)
				{
					outPut(Pw);
					return;
				}
				Q.push(Pw);
				vis[Pw.x][Pw.y] = true;
			}
		}
	}
}
int main()
{
	for(int i = 0; i < 5; ++i)
		for(int j = 0; j < 5; ++j)
			cin >> board[i][j];
	memset(vis,0,sizeof(vis));
	BFS(Point(0,0,0));
	//system("pause");
	return 0;
}
——————————————————————————————————————————————————————————————
另外一個就是點的輸出問題，采用回溯輸出
*/

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
bool vis[5][5],board[5][5];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int queHead,queTail;
struct Point
{
	int x,y,num;
	int father;
	Point(){};
	Point(int x_,int y_):x(x_),y(y_){};
	bool right()
	{
		if(x >= 0 && x < 5 && y >= 0 && y < 5 && num == 0)
			return true;
		return false;
	}
}Que[30];
void outPut(Point a)
{
	if(a.x == 0 && a.y == 0)
	{
		cout << "(0, 0)" << endl;
		return;
	}
	outPut(Que[a.father]);
	cout << "(" << a.x << ", " << a.y << ")" << endl;
}
void BFS(int x,int y,int num)
{
	queHead = queTail = 0;
	Point a(x,y);
	a.num = num;
	Que[queTail++] = a;
	vis[a.x][a.y] = true;
	for(;queHead < queTail; ++queHead)
	{
		for(int i = 0; i < 4; ++i)
		{
			Point Pw(Que[queHead].x +dx[i],Que[queHead].y + dy[i]);
			Pw.num = board[Pw.x][Pw.y];
			Pw.father = queHead;
			if(Pw.right() && !vis[Pw.x][Pw.y])
			{
				if(Pw.x == 4 && Pw.y == 4)
				{
					outPut(Pw);
					return;
				}
				Que[queTail++] = Pw;
				vis[Pw.x][Pw.y] = true;
			}
		}
	}
}
int main()
{
	for(int i = 0; i < 5; ++i)
		for(int j = 0; j < 5; ++j)
			cin >> board[i][j];
	memset(vis,0,sizeof(vis));
	BFS(0,0,0);
	system("pause");
	return 0;
}