UVA12825 - Happy Robot dp

题意:给定你机器的指令 L(左转) R(右转) F(直走) ?(前三项  未知),问你最终位置,x和y的范围/

解题思路:  dp[i][j]{MINX,MINY,MAXX,MAXY}  表示  到了第i个指令,方向 为 j(1-4)的最值, DP即可 。

解题代码:

  1 // File Name: d.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年10月21日 星期二 21时54分34秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 #define inf 1000000;
 26 using namespace std;
 27 char str[1004];
 28 int dp[1004][6][6];
 29 void print(int t)
 30 {
 31   for(int i = 1;i <= 4;i ++)
 32   {
 33      for(int j = 1;j <= 4;j ++)
 34          printf("%d ",dp[t][i][j]);
 35      printf("\n");
 36   }
 37   printf("\n");
 38 }
 39 void init(int t)
 40 {
 41     for(int i = 1;i <= 4 ;i ++)
 42         for(int j = 1;j <= 4;j ++ )
 43             if(j == 1 || j == 3)
 44             {
 45                 dp[t][i][j] = -inf;
 46             }else {
 47                 dp[t][i][j] = inf;
 48             }
 49 }
 50 int main(){
 51     int ca = 0 ;
 52     while(scanf("%s",str) != EOF)
 53     {
 54         ca ++ ; 
 55         init(0);
 56         for(int i = 1;i <= 4;i ++)
 57             dp[0][1][i] = 0 ;
 58         int len = strlen(str);
 59         int t = 0 ;
 60         //print(0);
 61         for(int i = 0 ;i < len ;i ++)
 62         {
 63             if(str[i] == R)
 64             {
 65                 for(int j = 1 ; j <= 4;j ++)
 66                     memcpy(dp[t][j-1],dp[t][j],sizeof(dp[0][0]));
 67                 memcpy(dp[t][4],dp[t][0],sizeof(dp[0][0]));
 68             }else if(str[i] == L){
 69                 for(int j = 4 ; j >= 1;j --)
 70                     memcpy(dp[t][j+1],dp[t][j],sizeof(dp[0][0]));
 71                 memcpy(dp[t][1],dp[t][5],sizeof(dp[0][0]));
 72             }else if(str[i] == F){
 73                 for(int j = 1;j <= 4;j ++)
 74                 {
 75                     if(j == 1)
 76                     {
 77                         dp[t][j][1] ++; 
 78                         dp[t][j][2] ++;
 79                     }else if(j == 2)
 80                     {
 81                         dp[t][j][3] ++; 
 82                         dp[t][j][4] ++;
 83                     }else if(j == 3)
 84                     {
 85                         dp[t][j][1] --; 
 86                         dp[t][j][2] --;
 87                     }else {
 88                         dp[t][j][3] --; 
 89                         dp[t][j][4] --;
 90                     }
 91                 }
 92             }else{
 93                 t ++ ; 
 94                 init(t);
 95                 int s1,s;
 96                 for(int j = 1;j <= 4 ;j ++)
 97                 {
 98                     int ne = (j == 4 ? 1:j + 1) ;
 99                     for(s = 1 ,s1 = 2; s <= 4l; s += 2, s1 += 2)
100                     {
101                         if(dp[t-1][j][s] > dp[t][ne][s])
102                         {
103                             dp[t][ne][s] = dp[t-1][j][s];
104                         }
105                         if(dp[t-1][j][s1] <  dp[t][ne][s1])
106                         {
107                             dp[t][ne][s1] = dp[t-1][j][s1];
108                         }
109                     }
110                     ne = (j == 1 ? 4:j - 1);
111                     for(s = 1 ,s1 = 2; s <= 4; s += 2, s1 += 2)
112                     {
113                         if(dp[t-1][j][s] > dp[t][ne][s])
114                         {
115                             dp[t][ne][s] = dp[t-1][j][s];
116                         }
117                         if(dp[t-1][j][s1] <  dp[t][ne][s1])
118                         {
119                             dp[t][ne][s1] = dp[t-1][j][s1];
120                         }
121                     }
122 
123                 }
124                 for(int j = 1;j <= 4;j ++) 
125                 {
126                     if(j == 1)
127                     {
128                         dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1] + 1);
129                         dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2] + 1);
130                         dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] );
131                         dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] );
132                     }else if(j == 2)
133                     {
134                         dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1]);
135                         dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2]);
136                         dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] + 1);
137                         dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] + 1);
138                     }else if(j == 3)
139                     {
140                         dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1] - 1);
141                         dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2] - 1);
142                         dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] );
143                         dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] );
144                     }else{
145                         dp[t][j][1] = max(dp[t][j][1],dp[t-1][j][1]);
146                         dp[t][j][2] = min(dp[t][j][2],dp[t-1][j][2]);
147                         dp[t][j][3] = max(dp[t][j][3],dp[t-1][j][3] - 1);
148                         dp[t][j][4] = min(dp[t][j][4],dp[t-1][j][4] - 1);
149                     }
150                 }
151             }
152 
153         //print(t);
154         }
155         int minx ,maxx,miny ,maxy;
156         minx = miny = inf;
157         maxx = maxy = -inf;
158         for(int j = 1;j <= 4;j ++)
159         {
160             if(dp[t][j][1] > maxx)
161                 maxx = dp[t][j][1];
162             if(dp[t][j][2] < minx)
163                 minx = dp[t][j][2];
164             if(dp[t][j][3] > maxy)
165                 maxy = dp[t][j][3];
166             if(dp[t][j][4] < miny)
167                 miny = dp[t][j][4];
168         }
169         printf("Case %d: %d %d %d %d\n",ca,minx,maxx,miny,maxy);
170     }
171     return 0;
172 }
View Code

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。