解題區/解題區 - UVa

UVa 12825 - Happy Robot

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

機器人一開始在原點 (0, 0)，並且面向東方 (East)。會按照以下三種指令做事。

  • L: turn left 方向往左轉，ex. 往北變成往西
  • R: turn right 方向往右轉，ex. 往北變成往東
  • F: go forward one step，依照當前方向往前走一步

指令中會有 ? 表示可以插入三種其中一種操作，請問機器人分別能走到的 x, y 最大最小值為何。

Sample Input

1
2
3
F?F
L??
LFFFRF

Sample Output

1
2
3
Case 1: 1 3 -1 1
Case 2: -1 1 0 2
Case 3: 1 1 3 3

Solution

動態規劃，把 x, y 分開考慮，同時維護 4 個方向的最大最小值。

定義 dp[i][dir][min/max] : 執行前 i 個指令，在 dir 方向上的最大最小值。

遞迴公式請參照代碼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int main() {
    char s[1024];
    int cases = 0;
    while (scanf("%s", s) == 1) {
        int dpx[1024][4][2], dpy[1024][4][2];
        // [N E S W][min/max]
        const int dx[4] = {0, 1, 0, -1};
        const int dy[4] = {1, 0, -1, 0};
        int n = strlen(s);
        for (int i = 0; i <= n; i++)
            for (int j = 0; j < 4; j++) {
                dpx[i][j][0] = INF, dpx[i][j][1] = -INF;
                dpy[i][j][0] = INF, dpy[i][j][1] = -INF;
            }
        dpx[0][1][0] = 0, dpx[0][1][1] = 0;
        dpy[0][1][0] = 0, dpy[0][1][1] = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'F' || s[i] == '?') {
                for (int j = 0; j < 4; j++) {
                    dpx[i+1][j][0] = min(dpx[i+1][j][0], dpx[i][j][0] + dx[j]);
                    dpx[i+1][j][1] = max(dpx[i+1][j][1], dpx[i][j][1] + dx[j]);
                    dpy[i+1][j][0] = min(dpy[i+1][j][0], dpy[i][j][0] + dy[j]);
                    dpy[i+1][j][1] = max(dpy[i+1][j][1], dpy[i][j][1] + dy[j]);
                }
            } 
            if (s[i] == 'R' || s[i] == '?') {
                for (int j = 0; j < 4; j++) {
                    dpx[i+1][(j+1)%4][0] = min(dpx[i+1][(j+1)%4][0], dpx[i][j][0]);
                    dpx[i+1][(j+1)%4][1] = max(dpx[i+1][(j+1)%4][1], dpx[i][j][1]);
                    dpy[i+1][(j+1)%4][0] = min(dpy[i+1][(j+1)%4][0], dpy[i][j][0]);
                    dpy[i+1][(j+1)%4][1] = max(dpy[i+1][(j+1)%4][1], dpy[i][j][1]);
                }
            }
            if (s[i] == 'L' || s[i] == '?') {
                for (int j = 0; j < 4; j++) {
                    dpx[i+1][(j+3)%4][0] = min(dpx[i+1][(j+3)%4][0], dpx[i][j][0]);
                    dpx[i+1][(j+3)%4][1] = max(dpx[i+1][(j+3)%4][1], dpx[i][j][1]);
                    dpy[i+1][(j+3)%4][0] = min(dpy[i+1][(j+3)%4][0], dpy[i][j][0]);
                    dpy[i+1][(j+3)%4][1] = max(dpy[i+1][(j+3)%4][1], dpy[i][j][1]);
                }
            }
//			for (int j = 0; j < 4; j++) {
//				printf("%d %d %d %d\n", dpx[i][j][0], dpx[i][j][1], dpy[i][j][0], dpy[i][j][1]);
//			}
//			puts("--");
        }
        int mnx = INF, mxx = -INF, mny = INF, mxy = -INF;
        for (int i = 0; i < 4; i++) {
            mnx = min(mnx, dpx[n][i][0]);
            mxx = max(mxx, dpx[n][i][1]);
            mny = min(mny, dpy[n][i][0]);
            mxy = max(mxy, dpy[n][i][1]);
        }
        printf("Case %d: %d %d %d %d\n", ++cases, mnx, mxx, mny, mxy);
    }
    return 0;
}