BFS——骑士的拯救行动

题目描述
公主被恶人抓走，被关押在牢房的某个地方。牢房用N*M (N, M <= 20)的矩阵来表示。矩阵中的每项可以代表道路（@）、墙壁（#）、和守卫（x）。
英勇的骑士（r）决定孤身一人去拯救公主（a）。我们假设拯救成功的表示是“骑士到达了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守卫，骑士一旦遇到守卫，必须杀死守卫才能继续前进。
现假设骑士可以向上、下、左、右四个方向移动，每移动一个位置需要1个单位时间，杀死一个守卫需要花费额外的1个单位时间。同时假设骑士足够强壮，有能力杀死所有的守卫。
给定牢房矩阵，公主、骑士和守卫在矩阵中的位置，请你计算拯救行动成功需要花费最短时间。
输入格式
第1行有两个整数代表N和M, (N, M <= 20).
随后N行，每行有M个字符。"@"代表道路，"a"代表公主，"r"代表骑士，"x"代表守卫, "#“代表墙壁。
输出格式
如果拯救行动成功，输出一个整数，表示行动的最短时间。
如果不可能成功，输出"Impossible”
输入样例1

#@#####@
#@a#@@r@
#@@#x@@@
@@#@@#@#
#@@@##@@
@#@@@@@@
@@@@@@@@ 

输出样例1
13
输入样例2

@x@@##x@#x@x#xxxx##@#x@x@@#x#@#x#@@x@#@x
xx###x@x#@@##xx@@@#@x@@#x@xxx@@#x@#x@@x@
#@x#@x#x#@@##@@x#@xx#xxx@@x##@@@#@x@@x@x
@##x@@@x#xx#@@#xxxx#@@x@x@#@x@@@x@#@#x@#
@#xxxxx##@@x##x@xxx@@#x@x####@@@x#x##@#@
#xxx#@#x##xxxx@@#xx@@@x@xxx#@#xxx@x#####
#x@xxxx#@x@@@@##@x#xx#xxx@#xx#@#####x#@x
xx##@#@x##x##x#@x#@a#xx@##@#@##xx@#@@x@x
x#x#@x@#x#@##@xrx@x#xxxx@##x##xx#@#x@xx@
#x@@#@###x##x@x#@@#@@x@x@@xx@@@@##@@x@@x
x#xx@x###@xxx#@#x#@@###@#@##@x#@x@#@@#@@
#@#x@x#x#x###@x@@xxx####x@x##@x####xx#@x
#x#@x#x######@@#x@#xxxx#xx@@@#xx#x#####@

输出样例2
7

这道题我本来是想用dfs的，结果wa了，原因是超时，因为dfs会遍历所有可能，耗时很多，于是我就换了个方法，选择用bfs来解决。
我们需要求的不是最短路径而是最短时间这点要注意。
所以我们可以开个数组记录从起点到每个点的最短时间，最后输出目的地的最短时间就可以了。
下面是代码，附加了注释

#include 
#include 
#include 
#define ll long long
#define mem(s, i) memset(s, i, sizeof(s))
#define INF 0x3f3f3f3f;
using namespace std;
int n, m;
char p[205][205];
int vim[205][205]; 
int a, b;
int d[2][4] = {{0, 0, 1, -1}, {1, -1, 0, 0}};
struct node
{
	int x, y; //点的坐标
	int len;  //起点到该点的距离
}head, tail;
bool check(int x, int y){//判断该点是否在地图范围内且不为城墙
	if(x >= 1&&x <= n&&y >= 1&&y <= m&&p[x][y]!='#')return true;
	return false;
}
void bfs(int xx, int yy, int l)
{
	queue q;
	head.x = xx, head.y = yy, head.len = l;
	vim[xx][yy] = 1;//该点初始都为1
	q.push(head);
	while(!q.empty()){
		tail = q.front();
		q.pop();
		
		for(int i = 0;i < 4;i++){
			head.x = tail.x+d[0][i];
			head.y = tail.y+d[1][i];
			if(check(head.x,head.y)){
				if(p[head.x][head.y] == 'x'){//守卫时间需要多+1
					head.len = tail.len+2;
				}
				else{
					head.len = tail.len+1;
				}
				if(vim[head.x][head.y]&&head.len>=vim[head.x][head.y]){
					//如果该点已被计算过并且到这个点的距离比之前记录的要大那么我们就跳过
					continue;
				}
				vim[head.x][head.y] = head.len;//更新时间
				q.push(head);//重新压入队列，以便后续使用
			}
		}
	}
}
void solve()
{
	cin >> n >> m;
	int x, y;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> p[i][j];
			if (p[i][j] == 'r')
				x = i, y = j; // qidian
			if (p[i][j] == 'a')
				a = i, b = j; // zhongdian
		}
	}
	bfs(x, y, 0);//起始时间我们从0开始
	if (vim[a][b])cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5154934.html