Tag:模板 BFS
Article From:https://www.cnblogs.com/huyufeifei/p/8462915.html

> this is the code of the year.

``` 1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <algorithm>
5 #include <cstdlib>
6 using namespace std;
7
8 int n,b,c;
9 int a[201];
10
11 int xiuxi(int now,int k)
12 {
13     if(k>200) return -1;
14     int aa=9999,bb=9999;
15     if(now == c) return k;
16
17     if(now+a[now]<=n)
18     {
19         aa=xiuxi(now+a[now],k+1);
20     }
21     if(now-a[now]>0)
22     {
23         bb=xiuxi(now-a[now],k+1);
24     }
25     ///return ???;
26 }
27
28 int main()
29 {
30     scanf ("%d%d%d",&n,&b,&c);
31     for(int i=1;i<=n;i++)
32     {
33         scanf ("%d",&a[i]);
34     }
35
36     int ans=xiuxi(b,0);
37     printf("%d",ans);
38     return 0;
39 }```

Code

today (2018.02.23) looks at this again and thinks of BFS after pretreatment. In fact, it’s just BFS. I don’t know why I choose the opposite.

this is the AC Code:

``` 1 #include <cstdio>
2 #include <cstring>
3 using namespace std;
4 ///P1135
5 int n,A,B,x;
6
7 int p[402],ptop,ptail=1;
8 bool vis[402];
9 int step[402];
10
11 struct floor{
12     int top,from[202];
13 }f[202];
14
15 void bfs(int now)
16 {
17     for(int i=1;i<=f[now].top;i++)
18     {
19         if(vis[f[now].from[i]]) continue;
20         vis[f[now].from[i]]=1;
21         p[++ptop]=f[now].from[i];
22         step[f[now].from[i]]=step[now]+1;
23         if(f[now].from[i]==A) return;
24     }
25     if(ptop==ptail-1) return;
26     ptail++;
27     bfs(p[ptail-1]);
28     return;
29 }
30
31 int main()
32 {
33     scanf ("%d%d%d",&n,&A,&B);
34     for(int i=1;i<=n;i++)
35     {
36         scanf ("%d",&x);
37         if(i-x>=1) f[i-x].from[++f[i-x].top]=i;
38         if(i+x<=n) f[i+x].from[++f[i+x].top]=i;
39     }
40     memset(step,-1,sizeof(step));
41
42     vis[B]=true;
43     step[B]=0;
44     p[++ptop]=B;
45
46     bfs(B);
47
48     printf("%d",step[A]);
49     return 0;
50 }```

ACCode

that’s the way it is. Good night, 11015.

``` 1 #include <cstdio>
2 #include <queue>
3 const int N = 210;
4
5 int n, b, a, k[N];
6 bool vis[N];
7
8 struct Sta {
9     int floor, step;
10     Sta(int f, int s) {
11         this->floor = f;
12         this->step = s;
13     }
14 };
15
16
17 void BFS() {
18     std::queue<Sta> Q;
19     Q.push(Sta(a, 0));
20     vis[a] = 1;
21     while(!Q.empty()) {
22         Sta s = Q.front();
23         Q.pop();
24         if(s.floor == b) {
25             printf("%d", s.step);
26             return;
27         }
28         int p = s.floor + k[s.floor];
29         if(p > 0 && p <= n && !vis[p]) {
30             vis[p] = 1;
31             Q.push(Sta(p, s.step + 1));
32         }
33         p = s.floor - k[s.floor];
34         if(p > 0 && p <= n && !vis[p]) {
35             vis[p] = 1;
36             Q.push(Sta(p, s.step + 1));
37         }
38     }
39     printf("-1");
40     return;
41 }
42
43 int main() {
44     scanf("%d%d%d", &n, &a, &b);
45
46     for(int i = 1; i <= n; i++) {
47         scanf("%d", &k[i]);
48     }
49
50     BFS();
51
52     return 0;
53 }```

2018Children’s Day special offer: new AC code, only 12 minutes!