博客

参考链接

分支限界法求解迷宫问题

题目内容

定义一个二维数组，例如：

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<queue>
using namespace std;
int ans[25];
int minnum=25;//到达终点时点的个数
struct dot {
	int n;//顶点标号
	int num;//顶点的值（0，1）
	int count;//当前路径的点数
	int temp[24];//当前路径
};
//出队函数
void Pop(queue<dot>* q);
//入队函数
void Push(queue<dot>* q, dot d);
void getAns(queue<dot>* q, dot d[], int pos);
int main() {
	dot d[25];
	for (int i = 0; i < 25; i++) {
		d[i].n = i;
		cin >> d[i].num;
		d[i].count = 1;
		d[i].temp[0] = 0;//起点为0
	}
	queue<dot>* q=new queue<dot>[25];//
	q->push(d[0]);//起点入队
	getAns(q, d, 0);
	for (int i = 0; i < minnum; i++) {
		int x = ans[i] / 5;
		int y = ans[i] % 5;
		cout <<"("<<x<<","<<y<<")" << endl;
	}
	delete[] q;
	return 0;
}
void Pop(queue<dot>* q) {
	q->pop();
}
void Push(queue<dot>* q, dot d) {
	q->push(d);
}
void getAns(queue<dot>* q, dot d[], int pos) {
	int i = 0;
	//如果已经到达终点
	if (pos == 24) {
		if (d[pos].count < minnum) {
			for (int i = 0; i < 25; i++) {
				ans[i] = d[pos].temp[i];
			}
			minnum = d[pos].count;
		}
		else
			return;
	}
	Pop(q);//当前起点出队
	if (d[pos].count > minnum) {
		return;//若已经大于最小点数还未到达终点，剪枝
	}
	//优先级：右、下、上、左  通过if限界
	if (pos % 5 != 4 && d[pos + 1].num != 1) {//不在右边界并且右边不为墙
		Push(q, d[pos + 1]);
		d[pos + 1].count = d[pos].count+1;
		for (i = 0; i < 25; i++) {
			d[pos + 1].temp[i] = d[pos].temp[i];
		}
		d[pos + 1].temp[d[pos + 1].count-1] = pos + 1;
		getAns(q, d, pos + 1);
	}
	if (pos / 5 != 4 && d[pos + 5].num != 1) {//不在下边界并且下方不为墙
		Push(q, d[pos + 5]);
		d[pos + 5].count = d[pos].count + 1;
		for (i = 0; i < 25; i++)
			d[pos + 5].temp[i] = d[pos].temp[i];
		d[pos + 5].temp[d[pos + 5].count-1] = pos + 5;
		getAns(q, d, pos + 5);
	}
	if (pos / 5 != 0 && d[pos - 5].num != 1) {//不在上边界
		Push(q, d[pos - 5]);
		d[pos - 5].count = d[pos].count + 1;
		for (i = 0; i < 25; i++)
			d[pos - 5].temp[i] = d[pos].temp[i];
		d[pos - 5].temp[d[pos - 5].count-1] = pos - 5;
		getAns(q, d, pos - 5);
	}
	if (pos % 5 != 0 && d[pos - 1].num != 1) {//不在左边界
		Push(q, d[pos - 1]);
		d[pos - 1].count = d[pos].count + 1;
		for (i = 0; i < 25; i++)
			d[pos - 1].temp[i] = d[pos].temp[i];
		d[pos - 1].temp[d[pos - 1].count-1] = pos - 1;
		getAns(q, d, pos - 1);
	}
}