【算法实验三】【分支限界法】【1042】电子老鼠闯迷宫

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。现给定一个起点S和一个终点T，求出电子老鼠最少要几步从起点走到终点。
 

 

输入

本题包含一个测例。在测例的第一行有四个由空格分隔的整数，分别表示起点的坐标S（x.y）和终点的坐标T（x,y）。从第二行开始的12行中，每行有12个字符，描述迷宫的情况，其中'X'表示建筑物，'.'表示路.

 

输出

输出一个整数，即电子老鼠走出迷宫至少需要的步数。

 

输入样例

2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX

 

输出样例

28

 

#include<iostream>

using namespace std;

int search();
bool isaim(int row, int col);
int takeoutofopen();
void addtoopen(int row, int col);
bool openempty();
bool canmoveto(int row, int col, int*r, int*c, int direction);
bool isused(int row, int col);
void readdata();

int open[1000]; // open表
int a[12][12];//-2表示墙，否则表示从起点走到这一点的最短步数，初始化位0；
int s, t;
int l, r;
int len = 1000;

int main() {
	readdata();
	cout << search() << endl;
}


int search() {
	while(!openempty()){
		int m = takeoutofopen();//从open表中取出并删除
		int r, c;
		int row = m / 12;
		int col = m % 12;
		int num = a[row][col];
		for (int i = 0; i < 4; i++) {
			if (canmoveto(row, col, &r, &c, i)) {
				if (isaim(r, c))
					return (num + 1);
				if (!isused(r, c)) {
					a[r][c] = num + 1;
					addtoopen(r, c);
				}
			}
		}
	}
}

bool isaim(int row, int col) {
	return (row * 12 + col == t);
}

int takeoutofopen() {
	if (l >= r) {
		printf("error: open is empty.");
		return -1;
	}
	int u = open[l++];
	l = l % len;
	return u;
}

void addtoopen(int row, int col) {
	int tmp = row * 12 + col;
	open[r++] = tmp;
	r = r % len;
}

bool openempty() {
	if (l > r) {
		printf("error: length of open is a minus number");
		return true;
	}
	return l == r ? true : false;
}

bool canmoveto(int row, int col, int* r, int* c, int direction) {
	switch (direction)
	{
	case 0: {row += 1; break; }
	case 1: {row -= 1; break; }
	case 2: {col += 1; break; }
	case 3: {col -= 1; }
	}
	*r = row;
	*c = col;
	if (row < 0 || row >= 12 || col < 0 || col >= 12){
		return false;
	}
	if (a[row][col] == 0)
		return true;
	return false;
}
bool isused(int row, int col) {
	return a[row][col] > 0;
}

void readdata() {
	int sr, sc, tr, tc;
	cin >> sr >> sc >> tr >> tc;
	for (int i = 0; i < 12; i++){
		for (int j = 0; j < 12; j++) {
			char k;
			cin >> k;
			if (k == 'X')
				a[i][j] = -2;//'X'表示墙，用-2表示
			else
				a[i][j] = 0; //'.'表示空格，用0表示。
		}
	}
	l = 0;
	r = 1;
	s = (sr - 1) * 12 + sc - 1;
	t = (tr - 1) * 12 + tc - 1;
	open[0] = s;
}