【2024.10.15练习】大胖子走迷宫

题目描述

---

题目思路 

在BFS进行状态转移时，除了四个方向外，还要转移到下一秒原来的位置（代表停留不动）。

---

我的代码

这里用数组代表在当前格子的时间。体型缩减用相对的墙壁变厚来等效替代。实际上只需要将队列的元素改成结构体，同时储存坐标、体积和时间就不需要这些多余的存储结构了。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
using namespace std;
typedef pair<int,int> P; 
const int MAX_N = 306;
int n;
int b;
int k;
char map_0[MAX_N][MAX_N];
char map_1[MAX_N][MAX_N];
char map_2[MAX_N][MAX_N];
int t[MAX_N][MAX_N]; //代表这一格上的时刻 
int marked[MAX_N][MAX_N]; //代表是否已搜索过 
queue<P> que;
void init_map(){
  for(int i=0;i<MAX_N;i++){
  for(int j=0;j<MAX_N;j++){
    map_0[i][j]='*';
    map_1[i][j]='*';
    map_2[i][j]='*';
}
  }
}
void widen(int i,int j){
  //墙壁扩展为3x3 
  for(int x=-1;x<=1;x++){
  for(int y=-1;y<=1;y++){
    if(i-x>0&&j-y>0) map_1[i-x][j-y]='*'; 
}
}
//墙壁扩展为5x5
  for(int x=-2;x<=2;x++){
    for(int y=-2;y<=2;y++){
    if(i-x>0&&j-y>0) map_2[i-x][j-y]='*'; 
}
}
}
void bfs(){
int dx[4]={-1,0,0,1};
int dy[4]={0,1,-1,0};
t[3][3]=0;
marked[3][3]=1;
que.push(P(3,3));
while(que.size()){
P p = que.front();
que.pop();
int x = p.first;
int y = p.second;
//判断是否走到终点
if(x==n-2&&y==n-2){
cout<<t[x][y];
return; 
}
for(int i=0;i<4;i++){//转移方向 
if(marked[x+dx[i]][y+dy[i]]!=1){  //未被搜索过 
if(map_2[x+dx[i]][y+dy[i]]!='*'&&t[x][y]<k){ //k秒内 
t[x+dx[i]][y+dy[i]]=t[x][y]+1;
marked[x+dx[i]][y+dy[i]]=1;
que.push(P(x+dx[i],y+dy[i]));
}else if(map_1[x+dx[i]][y+dy[i]]!='*'&&t[x][y]>=k&&t[x][y]<2*k){ //k~2k秒内 
t[x+dx[i]][y+dy[i]]=t[x][y]+1;
marked[x+dx[i]][y+dy[i]]=1;
que.push(P(x+dx[i],y+dy[i]));
}else if(map_0[x+dx[i]][y+dy[i]]!='*'&&t[x][y]>=2*k){  //2k秒后 
t[x+dx[i]][y+dy[i]]=t[x][y]+1;
marked[x+dx[i]][y+dy[i]]=1;
que.push(P(x+dx[i],y+dy[i]));
} 
} 
}
if(t[x][y]<2*k){//驻留 (额外的转移方向) 
 t[x][y]++;
 que.push(P(x,y)); 
} 
}
}
int main()
{
//预处理 
init_map();
    cin>>n>>k;
for(int i=1;i<=n;i++){
  for(int j=1;j<=n;j++){
    cin>>map_0[i][j];
    map_1[i][j] = map_0[i][j];
    map_2[i][j] = map_0[i][j];
}
 }
for(int i=0;i<=n+1;i++){
  for(int j=0;j<=n+1;j++){
    if(map_0[i][j]=='*') widen(i,j);
}
 } 
 //广搜 
 bfs();
  return 0;
}

原文地址：https://blog.csdn.net/FeAtherHZM/article/details/142957617

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！