88分一点TLE求助
  • 板块P2802 回家
  • 楼主User586768
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/7 20:04
  • 上次更新2023/11/3 05:19:52
查看原帖
88分一点TLE求助
586768
User586768楼主2023/8/7 20:04

第一个点不仅TLE,内存也差一点就爆了,求救

#include <bits/stdc++.h>
using namespace std;
int m,n;
short dx[4]={0,0,1,-1};
short dy[4]={1,-1,0,0};
int sx,sy,ex,ey;
int c[10][10];
void bfs(){
	queue<pair<pair<short,short>,pair<int,short> > > q;
	q.push(make_pair(make_pair(sy,sx),make_pair(0,6)));
	while(!q.empty()){
		pair<pair<short,short>,pair<int,short>> p=q.front();
		q.pop();
		if(p.second.second==0){
			continue;
		}
		if(c[p.first.first][p.first.second]==4){
			p.second.second=6;
		}
		p.second.second--;
		if(c[p.first.first][p.first.second]==3){
			printf("%d",p.second.first);
			exit(0);
		}
		if(p.second.first>=n*m-2){
			break;
		}
		p.second.first++;
		for(int i=0;i<4;i++){
			short xx=p.first.second+dx[i];
			short yy=p.first.first+dy[i];
			if(xx>=0&&xx<m&&yy>=0&&yy<n&&c[yy][xx]!=0){
				q.push(make_pair(make_pair(yy,xx),make_pair(p.second.first,p.second.second)));
			}
		}
	}
	printf("-1");
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&c[i][j]);
			if(c[i][j]==2){
				sx=j;
				sy=i;
			}
		}
	}
	bfs();
	return 0;
} 
2023/8/7 20:04
加载中...