hihocoder-1290-demo-day

发表于   |   分类于 ，   |  

题目大意

　　http://hihocoder.com/problemset/problem/1290

　　此题是微软2016校园招聘4月在线笔试的第三题。是一个机器人走迷宫的问题，你可以将迷宫任意位置的.变成b或者反之，机器人开始时向右走，遇到b以后向下走，再遇到b以后往右走，如此走法。求机器人从左上角走到右下角最少的变换次数。

题目分析

　　思路参考了这篇文章https://glatue.wordpress.com/2016/04/13/hihocoder-1290-demo-day-%E5%BE%AE%E8%BD%AF%E9%A2%98/

　　利用动态规划的思想，需要利用两个二维数组dpx和dpy，因为每个位置机器人的方向都可以是向右或者向下，代表从左上角走道当前位置最少需要变换的次数。

　　转移方程：

1
2
dpx[i][j] = min(dpx[i][j - 1], dpy[i][j - 1] + (matrix[i + 1][j - 1] != 'b')) + (matrix[i][j] == 'b');
dpy[i][j] = min(dpy[i - 1][j], dpx[i - 1][j] + (matrix[i - 1][j + 1] != 'b')) + (matrix[i][j] == 'b');

　　以第一个转移方程为例，含义是(i,j)位置向右方向的机器人一定是有(i,j-1)向右方向或者(i,j-1)向下方向并且(i+1,j-1)为b的机器人过来的，当然还要要求(i,j)不是b。第二个转移方程也同理。注意初始化的条件，为方便处理边界的dpx，dpy值都为最大值，但是dpx[1][0]一定要为0，因为初始条件是机器人在左上角向右走的，如果dpx[1][0]是最大值的话那么永远也得不到最少的变换次数了。

　　最后返回的是dpx[n][m]和 dpy[n][m]的最小值。

代码

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX_VALUE 102
#define MAX_DP 10002
using namespace std;
char matrix[MAX_VALUE][MAX_VALUE];
int dpx[MAX_VALUE][MAX_VALUE];
int dpy[MAX_VALUE][MAX_VALUE];
int find(int n, int m) {
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            dpx[i][j] = MAX_DP;
            dpy[i][j] = MAX_DP;
        }
    }
    dpx[1][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            dpx[i][j] = min(dpx[i][j - 1], dpy[i][j - 1] + (matrix[i + 1][j - 1] != 'b')) + (matrix[i][j] == 'b');
            dpy[i][j] = min(dpy[i - 1][j], dpx[i - 1][j] + (matrix[i - 1][j + 1] != 'b')) + (matrix[i][j] == 'b');
        }
    }
    return min(dpx[n][m], dpy[n][m]);
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    getchar();
    memset(matrix, 'b', sizeof(matrix));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%c", &matrix[i][j]);
        }
        getchar();
    }
    
    printf("%d\n", find(n, m));
    return 0;
}

　　时间复杂度O(n*m)

记忆化搜索版本
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 102
#define MAX_VALUE 20000
using namespace std;
char g[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE][2];
int N, M;
//direction
//0 -> right
//1 -> down
int search(const int x, const int y, const int direction) {
    if(x < 0 || y < 0 || x > N - 1 || y > M - 1) {
        return MAX_VALUE;
    }
    if(dp[x][y][direction] >= 0) {
        return dp[x][y][direction];
    }
    if(x == 0 && y == 0) {
        if(direction == 0) {
            dp[x][y][direction] = (g[x][y] == 'b');
        } else {
            dp[x][y][direction] = MAX_VALUE;
        }
        return dp[x][y][direction];
    }
    int res = (g[x][y] == 'b');
    //two options;
    int a, b, c, d;
    if(direction == 1) {
        if(x > 0) {
            a = search(x - 1, y, 0);
            if(y < M - 1) {
                a += (g[x - 1][y + 1] == '.');
            }
            b = search(x - 1, y, 1);
        } else {
            a = MAX_VALUE;
            b = MAX_VALUE;
        }
        dp[x][y][direction] = res + min(a, b);
    } else {
        if(y > 0) {
            c = search(x, y - 1, 0);
            d = search(x, y - 1, 1);
            if(x < N - 1) {
                d += (g[x + 1][y - 1] == '.');
            }
        } else {
            c = MAX_VALUE;
            d = MAX_VALUE;
        }
        dp[x][y][direction] = res + min(c, d);
    }
    return dp[x][y][direction];
}
int main() {
    scanf("%d%d", &N, &M);
    getchar();
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            scanf("%c", &g[i][j]);
        }
        getchar();
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            dp[i][j][0] = -1;
            dp[i][j][1] = -1;
        }
    }
    int a = search(N - 1, M - 1, 0);
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            dp[i][j][0] = -1;
            dp[i][j][1] = -1;
        }
    }
    int b = search(N - 1, M - 1, 1);
    //printf("a:%d,b:%d\n",a, b);
    printf("%d", min(a, b));
    return 0; 
}