不AC,想抄就抄

♻️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.......#
##########
*/

评论:

请先登录,才能进行评论