社区讨论

P1135奇怪的电梯 在已经加了限制条件的情况下TLE,求助大佬

题目总版参与者 4已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lo95iu5c
此快照首次捕获于
2023/10/28 05:54
2 年前
此快照最后确认于
2023/10/28 05:54
2 年前
查看原帖
数据9应该是 200 1 200 0 0 0 0 0 0 0 0 0......0 0 0 0(一共200个0)
我在代码中已经加入限制条件,如果目标楼层B没有别层的电梯可以到达的话,不进行DFS,直接输出-1 但是这个数据仍超时,不知道哪里出了问题
代码:
CPP
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;

int N,A,B,k,cnt=0x3f3f,cur=0;
int a[200][200];

void dfs(int i,int visited[]){
	
	if(i==B){
		if(cur<cnt) cnt=cur;
		return;
	}
		
	for(int j=1; j<=N; j++){	//j到达楼层 
		if(a[i][j]&&!visited[j]){
			visited[j]=1;	//访问过
			cur++;
			dfs(j,visited);
			cur--;
			visited[j]=0;
		
		}
	}
} 

int main(){
	
	scanf("%d%d%d",&N,&A,&B);
	int visited[N+1],flag=0;
	
	memset(a,0,sizeof(a));	//a[i][j] i->j是否可达
	memset(visited,0,sizeof(visited));
	
	
	for(int i=1; i<=N; i++){
		scanf("%d",&k);
		if(i+k<N+1&&k)		a[i][i+k]=1;
		if(i-k>0&&k) 	a[i][i-k]=1;
	}
	
	//任何楼层都到达不了B 
	for(int i=1; i<=N; i++){
		if(a[i][B]==1){
			flag=1;
			break;
		}
	}
	
	//有楼层可以到达B 
	if(flag){
		dfs(A,visited);
	}
	
	if(cnt==0x3f3f)
	printf("-1");
	else
	printf("%d",cnt);		
		
} 

回复

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

正在加载回复...