蓝桥杯2018年第九届真题-迷宫与陷阱

题目

题目链接

题解

BFS。

主要的特殊点在于加了很多特殊的情况，逐一判断即可。

注意vis/st标记数组是三维的第一维是行号，第二维是列号，第三维是能量值，表示是否以该能量值到达过该点。

代码

#include
using namespace std;
const int N = 1100;

int n, k, st[N*N][15];
string a[N];
int dir[2][4] = {-1, 1, 0, 0, 0, 0, -1, 1};

struct node {
	int first, second, third; // first：位置，second：能量值，third：步数 
};

int bfs () {
	queue  q;
	st[0][0] = 1;
	q.push ({0, 0, 0});
	
	while (q.size()) {
		node t = q.front ();
		int x = t.first / n; // x
		int y = t.first % n; // y
		int m = t.second; // 处于(x,y)位置的能量 
		int d = t.third; // 到达(x,y)的步数 
		q.pop ();
		if (x == n-1 && y == n-1) return d; // 终点 
		for (int i = 0;i > n >> k;
	for (int i = 0;i > a[i];
	
	cout