hdu 1548 A strange lift 와 이 드 검색 bfs + 우선 대기 열
10480 단어 우선 순위 대기 열
There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can't go up high than N,and can't go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you'll go up to the 4 th floor,and if you press the button "DOWN", the lift can't do it, because it can't go down to the -2 th floor,as you know ,the -2 th floor isn't exist.
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has to press the button "UP" or "DOWN"?
제목 설명: n 층 건물 (1 = n < = 200), 층 당 하나의 숫자 Ki 와 두 개의 버튼 UP 와 DOWN, 만약 당신 이 A 층 건물 에 있다 면 A 층 의 숫자 Ka = 3, 당신 은 UP 버튼 을 눌 러 A + Ka 층 건물 에 도착 하고 DOWN 버튼 을 눌 러 A - Ka 층 건물 에 도착 할 수 있 습 니 다 (전 제 는 A + Ka 와 A - Ka 가 모두 n 의 범위 안에 있다 는 것 입 니 다).지금 당신 은 A 층 에 있 습 니 다. 목적지 B 층 에 가 려 면 버튼 을 누 르 는 최소 횟수 를 물 어보 세 요.
알고리즘 분석: bfs 를 직접 검색 하면 됩 니 다. 최소 횟수 문제 와 관련 되 기 때문에 저 는 습관 적 으로 우선 대기 열 처 리 를 사 용 했 습 니 다.
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<cmath>
6 #include<algorithm>
7 #include<queue>
8 #define inf 0x7fffffff
9 using namespace std;
10 const int maxn=200+10;
11 const int M = 40000+10;
12
13 int n,A,B;
14 int an[maxn];
15 struct node
16 {
17 int cnt,id;
18 int value;
19 friend bool operator < (node a,node b)
20 {
21 return a.cnt > b.cnt;
22 }
23 }cur,tail;
24
25 int vis[maxn];
26 int bfs()
27 {
28 priority_queue<node> Q;
29 cur.id=A ;cur.cnt=0 ;
30 cur.value=an[A];
31 Q.push(cur);
32 memset(vis,0,sizeof(vis));
33 vis[A]=1;
34 int count=0;
35 while (!Q.empty())
36 {
37 cur=Q.top() ;Q.pop() ;
38 if (cur.id==B) return cur.cnt;
39
40 //cout<<cur.id<<" "<<an[cur.id]<<" "<<cur.cnt<<endl;
41 tail.id=cur.id+an[cur.id];
42 if (tail.id>=1 && tail.id<=n && !vis[tail.id])
43 {
44 tail.value=an[tail.id];
45 tail.cnt=cur.cnt+1;
46 vis[tail.id]=1;
47 Q.push(tail);
48 }
49
50 tail.id=cur.id-an[cur.id];
51 if (tail.id>=1 && tail.id<=n && !vis[tail.id])
52 {
53 tail.value=an[tail.id];
54 tail.cnt=cur.cnt+1;
55 vis[tail.id]=1;
56 Q.push(tail);
57 }
58 }
59 return -1;
60 }
61
62 int main()
63 {
64 while (scanf("%d",&n)!=EOF && n)
65 {
66 scanf("%d%d",&A,&B);
67 for (int i=1 ;i<=n ;i++) scanf("%d",&an[i]);
68 printf("%d
",bfs());
69 }
70 return 0;
71 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
색인 우선 대기 열: 최소 색인 우선 대기 열많은 응용 프로그램 에서 우선 대기 열 에 있 는 데 이 터 를 참조 할 수 있 습 니 다. 우 리 는 이러한 데이터 구 조 를 최소 요소 에 빠르게 접근 할 수 있 는 배열 로 볼 수 있 습 니 다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.