大胖子走迷宫

题目描述

小明是个大胖子，或者说是个大大胖子，如果说正常人占用 1 \times 11×1 的面积，小明要占用 5\times 55×5 的面积。

由于小明太胖了，所以他行动起来很不方便。当玩一些游戏时，小明相比小伙伴就吃亏很多。

小明的朋友们制定了一个计划，帮助小明减肥。计划的主要内容是带小明玩一些游戏，让小明在游戏中运动消耗脂肪。走迷宫是计划中的重要环节。

朋友们设计了一个迷宫，迷宫可以看成是一个由 n \times nn×n 个方阵组成的方阵，正常人每次占用方阵中 1 \times 11×1 的区域，而小明要占用 5 \times 55×5 的区域。小明的位置定义为小明最正中的一个方格。迷宫四周都有障碍物。

为了方便小明，朋友们把迷宫的起点设置在了第 33 行第 33 列，终点设置在了第 n−2n−2 行第 n−2n−2 列。

小明在时刻 00 出发，每单位时间可以向当前位置的上、下、左、右移动单位 1 的距离，也可以停留在原地不动。小明走迷宫走得很辛苦，如果他在迷宫里面待的时间很长，则由于消耗了很多脂肪，他会在时刻 kk 变成一个胖子，只占用 3 \times 33×3 的区域。如果待的时间更长，他会在时刻 2k2k 变成一个正常人，只占用 1 \times 11×1 的区域。注意，当小明变瘦时迷宫的起点和终点不变。

请问，小明最少多长时间能走到迷宫的终点。注意，小明走到终点时可能瘦了也可能没有变瘦。

输入描述

输入的第一行包含两个整数 n,k\ （1 \leq n \leq 300，1 \leq k \leq 1000）n,k （1≤n≤300，1≤k≤1000）。

接下来 nn 行，每行一个由 nn 个字符组成的字符串，字符为 + 表示为空地，字符为 \* 表示为阻碍物。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++

输出

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M

一开始想试试深搜，但觉得太复杂放弃了

// #include <iostream>
// using namespace std;
// char dp[310][310];
// int n,k,t=0;// int judge(int x,int y,int z)
// {
//   if(z==5)
//   {
//     for(int i=y-2;i<=y+2;i++)
//     if(dp[x][i]!='*')
//     return 0;//   }//   if(z==3)
//   {
//     for(int i=y-1;i<=y+1;i++)
//     if(dp[x][i]!='*')
//     return 0;
//   }//   return 1;
// }// void dfs(int x,int y)
// {
//    t++;
//   dp[x][y]='1';//表示走过// if(t<k)//每次相当于要有5格子的空间//相当于行和列都要先判断有没有这么大的空间
// {
//   if(judge(x-3,y,5))//上走
//   {//   }
//   if(judge(x+3,y,5))//下
//   {//   }
//   if(judge(x,y-3,5))//左
//   {//   }
//   if(judge(x,y+3,5))//右
//   {//   }//分情况讨论太复杂，效率太低// }
// else if(t>k&&t<2k)
// {
//    if(judge(x-2,y,3))//上走
//   {//   }
// }
// else
// {// }// bfs(x,y);// }
// int main()
// {//   cin>>n>>k;// for(int i=1;i<=n;i++)
// for(int j=1;j<=n;j++)
// {
//   cin>>dp[i][j];
// }// dfs(3,3);//   return 0;
// }//不会怎么处理胖子
//首先这么写很蠢，dfs不好判断前进范围，还要一一判断不同范围，还不如直接四个方向一个矩阵来的迅速//dfs一般用于有联系的，有前后关联紧密的才这么深度搜索，像迷宫这种大范围不确定的就用广搜bfs

过程加解析

#include <bits/stdc++.h>
using namespace std;
int dp[310][310];//插入地图
int vis[310][310];//标记走过的位置//地图和走过的位置还是要区分开最佳，不然比如胖子
//识别是否有障碍的时候，走过的标记和障碍会冲突//广搜核心:每一次都遍历了所有的情况，因此可以遍历所有的结果
//配合队列，队列的插入和删除保证为最佳情况（最短时间)
//以及队列能够使用出队来删去不满足条件的情况，减少无效遍历
//使用入队来实现继承满足条件的情况,继续遍历int n, k, stage;
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };//四个方向struct node
{int x;//行方向int y;//列int step;
};
//使用的时候自己命名一个node 的变量使用即可
queue<node>q;int check(int x, int y)
{for (int i = x - stage; i <= x + stage; i++)for (int j = y - stage; j <= y + stage; j++)//又给我忘记等号！//写循环时一定要判断等号要不要！{if (dp[i][j] == 1)return 0;}return 1;
}
//判断每个前进方向的那一排是否有障碍这么讨论太麻烦
//换成自身周围是否有障碍更简单
//周围没障碍我就只管往四方走。
//走下一步自身周围是否有障碍就能判断合不合法
//有时候思维不要过于直接，一种思路过于复杂可以试试
//另一种方式思考
void bfs()
{vis[3][3] = 1;//表示走过node now, next;//分现在和下一步的情况//注意next结点可以任意修改，但是now结点不能动,动了就全错now.x = now.y = 3;//不要忘记初始化结点！now.step = 0;//开局一定要注意插入第一个元素，//不然循环进不去!q.push(now);while (!q.empty())//q为空的时候返回真值，不空返回假{now = q.front();q.pop();if (now.x == n - 2 && now.y == n - 2)//遍历结尾{cout << now.step << endl;// return 0;//void 函数不要return 0;return;}if (now.step < k)//用选择次数代替时间,用step(每次的选择走哪时间也是增加1次，所以直接用)stage = 2;//表示还是大胖子else if (now.step >= k && now.step < 2 * k)stage = 1;elsestage = 0;//分为两种情况，原地踏步和往四方走if (stage > 0)//原地踏步，stage=0就不可能原地踏步//原地踏步的选择为下一步，不要投机取巧想着改一个step//你的一个地方的错误就会导致全盘错误，不要顾此失彼//因小失大！{// now.step=now.step+1;err//不能这么写，你这么写就改变了现在now的长度,//影响了后面的step的正确输出// 所以说还是分类最好.下一步归下一步，思路清晰不偷懒next.step = now.step + 1;next.x = now.x;next.y = now.y;q.push(next);}for (int i = 0; i < 4; i++){// next.x=now.x+dir[0][i];// next.y=now.y+dir[1][i];next.x = now.x + dir[i][0];next.y = now.y + dir[i][1];//四个方向讨论//列放了两个元素，分别四个方向//方向应该放在行，元素放在列，//其中一个元素为0是为了区分是移动y还是移动x//这么写很简洁，就一个循环都能实现x与y的移动//原理是动x的时候y不动即y+0;//动y不动x,x+0;//同时注意统一x,y方向(x一个下标,y一个)if (!check(next.x, next.y) || vis[next.x][next.y] || next.x - stage<1 || next.y - stage<1 || next.x + stage>n || next.y + stage>n)//    周围是否有障碍         是否走过                            是否已经超出迷宫continue;//设置边界,排除非法情况//  next.step++;不要这么写，会重复增加next.step = now.step + 1;//跟前面一样每次拿now结点就不会出错//增加移动距离vis[next.x][next.y] = 1;//别忘了标记走过！q.push(next);}}
}int main()
{cin >> n >> k;char c;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){cin >> c;//输入每次的符号if (c == '+')dp[i][j] = 0;elsedp[i][j] = 1;//1表示有障碍//将字符换成1，0，方便快捷}bfs();return 0;
}// 补充:原地踏步不可能在终点，所以不管先走还是后走你都要在下一轮再次判断。
// 因为这也算一种情况——他可以等瘦下来再往原本走不了的捷径走。
// 但是不影响，原地踏步相当于放弃这一轮可能到达终点的权利，不可能会优先被输出，所以放在哪都行。// 而且队列永远都是后面的情况在队尾插入，所以就保证了轮数少的一定先被输出。// 将判断前行的路的是否有障碍转变为下一步自己的占地面积是否有障碍，更好理解和写出代码。（都是一样的，占地面积更好编写）

补充

#include <bits/stdc++.h>
using namespace std;
int maze[305][305];
int vis[305][305];
int n, k, state;  // state 是当前小明的状态，2是大胖子，1是胖子，0是正常人
int dir[4][2] = { {1,0}, {-1,0}, {0, 1}, {0, -1} };struct node
{int x, y, step;node(int a, int b, int c){x = a;y = b;step = c;}
};
queue< node > q;int check(int x, int y) // 判断小明占地面积里有没有障碍
{for (int i = x - state; i <= x + state; i++)for (int j = y - state; j <= y + state; j++)if (!maze[i][j]) return 0;return 1;
}int main()
{cin >> n >> k;char c;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){cin >> c;if (c == '+')  maze[i][j] = 1;else  maze[i][j] = 0;}q.push(node(3, 3, 0));vis[3][3] = 1;while (!q.empty()){node u = q.front();q.pop();int x = u.x, y = u.y, s = u.step;if (x == n - 2 && y == n - 2){cout << s;return 0;}if (s < k) state = 2;else if (s >= k && s < 2 * k)  state = 1;  // 瘦成胖子else if (s >= 2 * k) state = 0;   // 瘦成正常人if (state > 0)  // 原地踏步{u.step = u.step + 1;q.push(u);}for (int i = 0; i < 4; i++){int dx = x + dir[i][0], dy = y + dir[i][1];if (!check(dx, dy) || vis[dx][dy] || dx - state < 1 || dx + state > n || dy - state < 1 || dy + state > n) continue;q.push(node(dx, dy, s + 1));vis[dx][dy] = 1;}}return 0;
}