1001.HowcanIgo?（soj）（bfs或者dp）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

Description

In the year 2012, Departyment finally finished building Freedam. From then on, all people can only smilence in the Chintranet. If you want to go some where, you need to obey some rules.

One day, Shitizen wants to go somewhere. He(/she/it?) starts from (X, 0), and wants to go to any place where y-coordinate is H. Thanks to Freedam, Shitizen can only move in 3 directions: up-left, up-right, up. That is to say, if Shitizen is at (x, y), he can only move to (x + 1, y + 1), (x - 1, y + 1) or (x, y + 1) in one step. Moreover, when Shitizen wants to move to (x, y), he must ensure that x is in the range of [Ly, Ry]. After one move, if his x-coordinate has changed, it will cost Shitizen 1 Yakshit. Shitizen wants to know if he can reach his destination. If yes, he wants know the minimal Yakshit cost.

Input

The first line is an integer T (1 ≤ T ≤ 20), the number of test cases.

In each test cases, the first line is an integer H, the y-coordinate Shitizen wants to reach.

The second line has H numbers, R_1, R_2 ... R_H.

The third line has another H numbers, L_1, L_2 ... L_H.

The forth line has one integer X, the x-coordinate of the start location.

It's guaranteed that 1 ≤ H ≤ 1000, 0 ≤ X, L_i, R_i ≤ 1000.

Output

For each test case, output an integer in a line.

If poor Shitizen can't reach his destination, output -1.

Otherwise, output the minimal Yakshit cost.

Sample Input

Copy sample input to clipboard

2
5
10 10 10 5 10
4 0 4 0 0
8
5
10 4 6 9 3
3 3 2 5 1
5

Sample Output

3
-1

不多说上代码：

 1 // Problem#: 8047
 2 // Submission#: 2066467
 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University
 6 #include<iostream>
 7 #include<stdio.h>
 8 #include<math.h>
 9 #include<algorithm>
10 #include<string.h>
11 #include<string>
12 #include<ctime>
13 #include<queue>
14 #include<list>
15 #include<map>
16 #include<set>
17 #include<vector>
18 #include<stack>
19 #define INF 999999999
20 #define MAXN 10000000
21 using namespace std;
22 int L[1010],R[1010],h;
23 int mark[1010][1010];
24 int cost[1010][1010];
25 struct Nod
26 {
27     int x,y;
28     int cost;
29 }d,p;
30 
31 int cx[]={0,-1,1};
32 int cy[]={1,0,0};
33 
34 int bfs(int x)
35 {   
36     memset(mark,0,sizeof(mark));
37     memset(cost,0,sizeof(cost));
38     queue<Nod> q;
39     d.cost=0;
40     d.x=x;
41     d.y=0;
42     mark[x][0]=1;
43     q.push(d);
44     int maks=INF;
45     while(!q.empty())
46     {
47         p=q.front();
48         q.pop();
49         if(p.y==h&&maks>p.cost)
50             maks=p.cost;
51         int i;
52         for(i=0;i<3;i++)
53         {
54             d.x=p.x+cx[i];
55             d.y=p.y+cy[i];
56             if(d.x>=L[d.y]&&d.x<=R[d.y]&&!mark[d.x][d.y])
57             {   
58                 d.cost=p.cost;
59                 if(d.x!=p.x)
60                 {
61                     d.cost=p.cost+1;
62                 }
63                 mark[d.x][d.y]=1;
64                 q.push(d);
65             }
66         }
67     }
68     return maks;
69 }
70 int main()
71 {
72     int t;
73     scanf("%d",&t);
74     while(t--)
75     {
76         scanf("%d",&h);
77         int i;
78         for(i=1;i<=h;i++)
79             scanf("%d",&R[i]);
80         for(i=1;i<=h;i++)
81             scanf("%d",&L[i]);
82         int x;
83         scanf("%d",&x);
84         int res=bfs(x);
85         if(res==INF)
86             res=-1;
87         printf("%d\n",res);
88     }
89     return 0;
90 }

dp：

 1 // Problem#: 8047
 2 // Submission#: 2066559
 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University
 6 #include<iostream>
 7 #include<algorithm>
 8 #include<cstring>
 9 #include<cstdio>
10 #include<vector>
11 using namespace std;
12 int l[1010],r[1010],map[2][1010];
13 int main()
14 {    
15     int t;
16     while(scanf("%d",&t)!=EOF)
17         while(t--)
18         {
19             int h,i,j;
20             memset(map,-1,sizeof(map));
21             scanf("%d",&h);
22             for(i=0;i<h;i++)
23                 scanf("%d",&r[i]);
24             for(i=0;i<h;i++)
25                 scanf("%d",&l[i]);
26             int k=0,x;
27             scanf("%d",&x);
28             map[k][x]=0;
29             k=1-k;
30             int flag;
31             for(i=0;i<h;i++,k=1-k)
32             {
33                 flag=0;
34                 memset(map[k],-1,sizeof(map[k]));
35                 for(j=l[i];j<=r[i];j++)
36                 {
37                     if(map[1-k][j+1]!=-1&&(map[k][j]==-1||map[k][j]>map[1-k][j+1]+1))
38                     {
39                         flag=1;
40                         map[k][j]=map[1-k][j+1]+1;
41                     }
42                     if(map[1-k][j-1]!=-1&&j!=0&&(map[k][j]==-1||map[k][j]>map[1-k][j-1]+1))
43                     {
44                         flag=1;
45                         map[k][j]=map[1-k][j-1]+1;
46                     }
47                     if(map[1-k][j]!=-1&&(map[k][j]==-1||map[k][j]>map[1-k][j]))
48                     {
49                         flag=1;
50                         map[k][j]=map[1-k][j];
51                     }
52                 }
53                 //for(j=0;j<=10;j++)
54                 //    printf("%d ",map[k][j]);
55                 //printf("\n");
56                 if(flag==0)
57                     break;
58             }
59             if(i<h)
60                 printf("-1\n");
61             else
62             {
63                 k=1-k;
64                 int max=0xffff-1;
65                 for(i=l[h-1];i<=r[h-1];i++)
66                     if(max>map[k][i]&&map[k][i]!=-1)
67                         max=map[k][i];
68                 printf("%d\n",max);
69             }
70         }
71     return 0;
72 }