社区讨论

为啥TLE,求助

P2802回家参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7dcggf
此快照首次捕获于
2025/11/20 19:49
4 个月前
此快照最后确认于
2025/11/20 19:49
4 个月前
查看原帖
https://www.luogu.org/recordnew/show/14050989
CPP
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int m,n;
int bx,by,ex,ey;
int a[10][10];
int dx[5]={0,-1,0,1},dy[5]={1,0,-1,0};
int t=inf;
void dfs1(int x,int y,int life,int times){
	if(times>m*n||times>=t||life==0) return;
	if(life==1&&a[x][y]!=4)	return;
	if(x==ex&&y==ey) {
		t=min(t,times);
		return;
	}
	if(a[x][y]==4) life=6;
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]!=0){
			dfs1(xx,yy,life-1,times+1);
		}
	}
}
void dfs2(int x,int y,int life,int times){
	if(times>m*n||times>=t||life==0) return;
	if(life==1&&a[x][y]!=4)	return;
	if(x==bx&&y==by) {
		t=min(t,times);
		return;
	}
	if(a[x][y]==4) life=6;
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]!=0){
			dfs2(xx,yy,life-1,times+1);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	scanf("%d",&a[i][j]);
	  	if(a[i][j]==2) bx=i,by=j;
		if(a[i][j]==3) ex=i,ey=j;
	  }
	if(ey<by) dfs2(ex,ey,6,0);
	else dfs1(bx,by,6,0); 
//	dfs1(bx,by,6,0);
	if(t!=inf) printf("%d",t);
	else printf("-1");
	
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...