♻️lzhh_lzhh32 • 5个月前
/*
BFS时
除了箱子要按人->箱的方向推一格外,还要考虑人从箱子的某个相邻位置出发,能到达的那些箱子的相邻位置
*/
#include<bits/stdc++.h>
using namespace std;
struct point{
int x,y;
}endb,startp;
int n,m;
char s[905][905];
bool pcan[905][905]; //表示从初始位置到i行j列需要多少步 ,没到的记为0,初始位置记为1,输出答案时-1即可
int bmov[905][905];
point exc(int x,int y){ //把两个坐标转成point型
point p;
p.x=x;
p.y=y;
return p;
}
void pcgo(point node,point boxnow){ //更新pcan,表示人可以走到的点,node为人当前所在点
if(node.x==boxnow.x&&node.y==boxnow.y) return;
if(s[node.x][node.y+1]!='#'&&pcan[node.x][node.y+1]==0){
pcan[node.x][node.y+1]=1;
pcgo(exc(node.x,node.y+1),boxnow);
}
if(s[node.x][node.y-1]!='#'&&pcan[node.x][node.y-1]==0){
pcan[node.x][node.y-1]=1;
pcgo(exc(node.x,node.y-1),boxnow);
}
if(s[node.x+1][node.y]!='#'&&pcan[node.x+1][node.y]==0){
pcan[node.x+1][node.y]=1;
pcgo(exc(node.x+1,node.y),boxnow);
}
if(s[node.x-1][node.y]!='#'&&pcan[node.x-1][node.y]==0){
pcan[node.x-1][node.y]=1;
pcgo(exc(node.x-1,node.y),boxnow);
}
}
queue<point> q; //存储箱子可以走的节点
int main(){
cin>>n>>m; //n行m列
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>s[i][j];
if(s[i][j]=='B'){ //箱子始
point p;
p.x=i;
p.y=j;
q.push(p);
bmov[i][j]++;
}else if(s[i][j]=='T'){ //箱子终
endb.x=i;
endb.y=j;
}else if(s[i][j]=='S'){ //人始
startp.x=i;
startp.y=j;
}
}
}
//读入结束,下面bfs
/*
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<pcan[i][j];
}
cout<<endl;
}
*/
while(!q.empty()&&bmov[endb.x][endb.y]==0){
point node=q.front();
q.pop();
s[node.x][node.y]='#'; //提前把箱子点标记为障碍物
pcgo(startp,node);
s[node.x][node.y]='.';
//遍历上下左右四个点,如果该点人能到达,就推
point boxnow;
if(pcan[node.x+1][node.y]/*有人*/&&bmov[node.x-1][node.y]==0/*要推的位置为空*/&&s[node.x-1][node.y]!='#'){ //人下
bmov[node.x-1][node.y]=bmov[node.x][node.y]+1; //等于前一步加一
boxnow=exc(node.x-1,node.y);
startp=exc(node.x,node.y);
s[boxnow.x][boxnow.y]='#';
q.push(boxnow);
pcgo(startp,boxnow); //更新人能走到的
s[boxnow.x][boxnow.y]='.';
}
if(pcan[node.x-1][node.y]/*有人*/&&bmov[node.x+1][node.y]==0&&s[node.x+1][node.y]!='#'){ //人上
bmov[node.x+1][node.y]=bmov[node.x][node.y]+1; //等于前一步加
boxnow=exc(node.x+1,node.y);
startp=exc(node.x,node.y);
s[boxnow.x][boxnow.y]='#';
q.push(boxnow);
pcgo(startp,boxnow); //更新人能走到的
s[boxnow.x][boxnow.y]='.';
}
if(pcan[node.x][node.y+1]/*有人*/&&bmov[node.x][node.y-1]==0&&s[node.x][node.y-1]!='#'){ //人右
bmov[node.x][node.y-1]=bmov[node.x][node.y]+1; //等于前一步加一
boxnow=exc(node.x,node.y-1);
startp=exc(node.x,node.y);
s[boxnow.x][boxnow.y]='#';
q.push(boxnow);
pcgo(startp,boxnow); //更新人能走到的
s[boxnow.x][boxnow.y]='.';
}
if(pcan[node.x][node.y-1]/*有人*/&&bmov[node.x][node.y+1]==0&&s[node.x][node.y+1]!='#'){ //人左
bmov[node.x][node.y+1]=bmov[node.x][node.y]+1; //等于前一步加一
boxnow=exc(node.x,node.y+1);
startp=exc(node.x,node.y);
s[boxnow.x][boxnow.y]='#';
q.push(boxnow);
pcgo(startp,boxnow); //更新人能走到的
s[boxnow.x][boxnow.y]='.';
}
s[node.x][node.y]='.';
}
cout<<bmov[endb.x][endb.y]-1<<endl;
return 0;
}
/*
10 10
##########
#T..#...##
#...#...##
#...#...##
#...#...##
#....B...#
#..##.####
###......#
#S.......#
##########
*/
评论:
请先登录,才能进行评论