蓝桥杯2019年第十届国赛真题-大胖子走迷宫

题目

题目链接

题解

BFS。

整体思路：将位置信息和时刻信息放入队列，根据时刻信息判断当前时刻小明的大小，如果大小为 1 × 1 1×1 1×1则不能原地停留，因为没意义啊，停留是为了让自己的肚子减小，但是 1 × 1 1×1 1×1时肚子已经最小了，所以只有当大小不是 1 × 1 1×1 1×1时才会进行停留操作，对应到代码上就是位置信息不变，时刻信息+1入队；其他部分就是和基础BFS差不多了，遍历四个方向，如果挺着当前的肚子会遇到障碍，则continue；如果之前走到过该位置，则continue；如果肚子发生越界，则continue。到达终点结束。

真没想到对于原地停留如此处理！而且标记数组居然只用标记位置信息！

代码

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

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

struct node {
	int first; // 位置（一维） 
	int second; // 到达该位置的时间 
	// 不记录小明每个位置的大小，大小可由时间来判断 
};

int bfs () {
	
	queue  q;
	q.push ({2 * n + 2, 0});
	
	st[2*n+2] = 1; // 标记起点 
	
	while (q.size()) {
		
		node t = q.front ();
		q.pop ();
		
		int x = t.first / n;
		int y = t.first % n;
		int tm = t.second;
		
		// 如果当前小明大小不是1 ×1，那么小明可以选择原地踏步 
		int v = 2; // 大小记录为多出的宽度，即5 ×5 = (2*v+1) * (2*v+1)，其中v=2，类似的 3 ×3 = (2*1+1) * (2*1+1)
		if (tm >= 2*k) v = 0;
		else if (tm >= k) v = 1;
		if (v) q.push ({t.first, tm + 1}); // 位置不变，时间增加 
		// 放在遍历四个方向的for循环外面 
		
		for (int i = 0;i > k;
	for (int i = 0;i > a[i];
	
	cout