大胖子走迷宫

2024-03-06 18:36

文章标签 迷宫胖子

本文主要是介绍大胖子走迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：0大胖子走迷宫 - 蓝桥云课 (lanqiao.cn)

直接上代码：（该代码借鉴的是题解中博主谦言万语的代码）

#include<iostream>
#include<queue>
using namespace std;
char map[310][310];//地图 
int vis[310][310];//标记数组
int n,k,t;//n行数，k时间，t小明的体型 
//上下左右 
const int dr[]={0,0,1,-1};
const int dc[]={-1,1,0,0};//存放节点的位置x，y，并且记录所所用时间 
typedef struct node{int x,y,dis; node(int x=0,int y=0,int dis=0):x(x),y(y),dis(dis) {}
}node; //判断小明是否还在里面 
bool isInside(int dx,int dy)
{if(dx>=t/2&&dx<=n-t/2-1&&dy>=t/2&&dy<=n-t/2-1)return true;return false;
}//判断小明是否被障碍物卡住 
bool isKa(int dx,int dy)
{for(int i=dx-t/2;i<=dx+t/2;i++){for(int j=dy-t/2;j<=dy+t/2;j++){if(map[i][j]=='*') return true;}}return false;	
}//广度优先搜索BFS 
void bfs()
{queue<node> q;//队列node u(2,2,0);//初始节点 vis[2][2]=1;//标记起点 q.push(u);//初始节点进栈while(!q.empty()){node u=q.front();//记录目前的节点 q.pop();//节点出栈//到达终点，结束 if(u.x==n-3&&u.y==n-3)//位置都是从0开始标记，所以此时终点位置在(n-3,n-3) {cout<<u.dis;return;} //记录小明的体型 if(u.dis<k) t=5;else if(u.dis>=k&&u.dis<2*k)t=3;else if(u.dis>=2*k) t=1; if(t!=1)q.push(node(u.x,u.y,u.dis+1));//当体型大时，假设小明就在此等待身体缩小 //遍历四个方向 for(int i=0;i<4;i++){int nx=u.x+dr[i];int ny=u.y+dc[i];if(isInside(nx,ny)&&!vis[nx][ny]&&!isKa(nx,ny))//移动位置时，确保小明还能在范围内且该地没被走过且此地没有障碍物 {vis[nx][ny]=1;node v(nx,ny,u.dis+1);q.push(v);}} } 
}
int main()
{cin>>n>>k;for(int i=0;i<n;i++)cin>>map[i];bfs();return 0;
}