求助!!bfs写法84分,求大佬看看,哪里被卡了啊
  • 板块P2802 回家
  • 楼主280123xxx
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/31 23:40
  • 上次更新2023/11/3 06:39:32
查看原帖
求助!!bfs写法84分,求大佬看看,哪里被卡了啊
1037624
280123xxx楼主2023/7/31 23:40
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int g[N][N];//存地图 
bool st[N][N];//表示地图点的状态 
int d[N][N];//存每个点的到起点的最短距离 
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
queue<pair<int,int>> q;
int n,m;
int xue[N][N];
int main()
{
  bool flag=false;//回家状态 
  cin>>n>>m;
  int qx,qy,zx,zy;//起点坐标和终点坐标 
  for(int i=1;i<=n;i++)
  {
  	for(int j=1;j<=m;j++)
  	{
  		cin>>g[i][j];
  		if(g[i][j]==2)
		  {
		  	qx=i,qy=j;
		  } 
		if(g[i][j]==3)
		{
			zx=i,zy=j;
		}
	}
  }
    q.push({qx,qy});
	st[qx][qy]=true;
	xue[qx][qy]=6;
	while(!q.empty())
	{  
        auto t=q.front();
		q.pop();
		int x=t.first,y=t.second;
		if(x==zx&&y==zy&&xue[zx][zy]>=1) //到家 ,还活着。尸体运回家不算 
		{
			flag=true;
			break;
		} 
		for(int i=0;i<4;i++)
		{
			int X=x+dx[i],Y=y+dy[i];
			if(X>=1&&X<=n&&Y>=1&&Y<=m&&!st[X][Y]&&g[X][Y]!=0)
			{   
				xue[X][Y]=xue[x][y]-1;//更新血量 
				if(xue[X][Y]==0) {cout<<-1<<endl; return 0;}//途中暴毙,输出-1 
				st[X][Y]=true; 
				q.push({X,Y});
				if(g[X][Y]==4) xue[X][Y]=6;//空地上舔血包 
				d[X][Y]=d[x][y]+1;//更新新点的步数 
			}
	    }
    }  
    if(!flag) cout<<-1<<endl;
    else cout<<d[zx][zy]<<endl;
    return 0; 
  
} 
2023/7/31 23:40
加载中...