社区讨论
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 条回复,欢迎继续交流。
正在加载回复...