用堆棧實(shí)現(xiàn)迷宮問題，二維數(shù)組表示迷宮：1表示墻壁，0表示可以走的路，只能橫著走或豎著走

成都創(chuàng)新互聯(lián)公司是專業(yè)的大關(guān)網(wǎng)站建設(shè)公司，大關(guān)接單;提供成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì),網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行大關(guān)網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

不能斜著走，要求編程實(shí)現(xiàn)找到從左上角到右下角的路線

//深度優(yōu)先：有解就退出搜索（不一定是最優(yōu)解）
#include
#include
using namespace std;
#define ROW 5
#define COL 5
typedef struct point
{
	int _row;
	int _col;
}Point;
Point stack[512];
int top= 0;
void Push(Point& p)
{
	stack[top++] = p;
}
const Point& Pop()
{
	return stack[--top];
}
int IsEmpty()
{
	return top==0;
}
int maze[ROW][COL] = {
		{ 0, 0, 0, 0, 0 },
		{ 0, 1, 1, 1, 0 },
		{ 0, 1, 1, 0, 0 },
		{ 0, 1, 1, 0, 1 },
		{ 0, 0, 0, 0, 0 },
};
void PrintMaze()
{
	for (int i = 0; i < ROW; ++i)
	{
		for (int j = 0; j < COL; ++j)
		{
			cout << maze[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
Point Prev[ROW][COL] = {
		{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
		{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
		{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
		{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
		{ { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 } },
};
void Visit(int row, int col,Point& p)
{
	Point tmp = { row, col};
	maze[row][col] = 2;
	Prev[row][col] = p;
	Push(tmp);
}
void Test1()
{
	Point p = { 0, 0};
	maze[p._row][p._col] = 2;
	Push(p);

	while (!IsEmpty())
	{
		p = Pop();
		if (p._row == ROW - 1 && p._col == COL - 1)
			break;

		//up
		if (p._row - 1 >= 0 && maze[p._row - 1][p._col] == 0)
			Visit(p._row - 1, p._col,p);
		//down
		if (p._row + 1 < ROW&&maze[p._row + 1][p._col] == 0)
			Visit(p._row + 1, p._col,p);
		//left
		if (p._col - 1 >= 0 && maze[p._row][p._col - 1] == 0)
			Visit(p._row, p._col - 1,p);
		//right
		if (p._col + 1 < COL&&maze[p._row][p._col + 1] == 0)
			Visit(p._row, p._col + 1,p);
	}
	if (p._row == ROW - 1 && p._col == COL - 1)
	{
		printf("(%d,%d)\n", p._row, p._col);
		while ((Prev[p._row][p._col])._row != -1)
		{
			p = Prev[p._row][p._col];
			printf("(%d,%d)\n", p._row, p._col);
		}
	}
	else
		cout << "no path!\n";
}

//廣度求得最優(yōu)路徑，找到后停止搜索
#include
using namespace std;
#define ROW 5
#define COL 5
typedef struct point
{
	int _row;
	int _col;
	int _prev;
}Point;
Point queue[512];
int head = 0;
int tail = 0;
void Enqueue(Point& p)
{
	queue[tail++] = p;
}
const Point& Dequeue()
{
	return queue[head++];
}
int IsEmpty()
{
	return head == tail;
}
int maze[ROW][COL] = {
		{ 0, 0, 0, 0, 0 },
		{ 0, 1, 1, 1, 0 },
		{ 0, 1, 1, 0, 0 },
		{ 0, 1, 1, 0, 1 },
		{ 0, 0, 0, 0, 0 },
};
void PrintMaze()
{
	for (int i = 0; i < ROW; ++i)
	{
		for (int j = 0; j < COL; ++j)
		{
			cout << maze[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void Visit(int row, int col)
{
	Point tmp = { row, col, head - 1 };
	maze[row][col] = 2;
	Enqueue(tmp);
}
void Test1()
{
	Point p = { 0, 0, -1 };
	maze[p._row][p._col] = 2;
	Enqueue(p);

	while (!IsEmpty())
	{
		p = Dequeue();
		if (p._row == ROW - 1 && p._col == COL - 1)
			break;
         
		//up
		if (p._row - 1 >= 0 && maze[p._row - 1][p._col] == 0)
			Visit(p._row - 1, p._col);
		//down
		if (p._row + 1 < ROW&&maze[p._row + 1][p._col] == 0)
			Visit(p._row + 1, p._col);
		//left
		if (p._col - 1 >= 0 && maze[p._row][p._col - 1] == 0)
			Visit(p._row, p._col - 1);
		//right
		if (p._col + 1 < COL&&maze[p._row][p._col + 1] == 0)
			Visit(p._row, p._col + 1);
	}
	if (p._row == ROW - 1 && p._col == COL - 1)
	{
		printf("(%d,%d)\n", p._row, p._col);
		while (p._prev != -1)
		{
			p = queue[p._prev];
			printf("(%d,%d)\n", p._row, p._col);
		}
	}
	else
		cout << "no path!\n";
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

分享題目：迷宮問題的求解方式：應(yīng)用深度優(yōu)先和廣度優(yōu)先的搜索-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://weahome.cn/article/hpigj.html