微软2016实习生笔试题--Demo Day

题目：Demo Day
描述：You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out.
The maze consists of N * M grids. Each grid is either empty(represented by ‘.’) or blocked by an obstacle(represented by ‘b’). The robot will be release at the top left corner and the exit is at the bottom right corner.
Unfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can’t and keep moving to the bottom until it can’t. At the beginning, the robot keeps moving to the right.

rrrrbb..
…r…. ====> The robot route with broken sensors is marked by ‘r’.
…rrb..
…bb…

While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?

输入
Line 1: N, M.
Line 2-N+1: the N M maze.
For 20% of the data, N M <= 16.
For 50% of the data, 1 <= N, M <= 8.
For 100% of the data, 1<= N, M <= 100.

输出
The minimum number of grids to be changed.

样例输入

4 8
….bb..
……..
…..b..
…bb…

样例输出

1

使用动态规划求解，dp[i][j][0]代表机器人从起点到达点(i, j)时方向为右的最小修改次数，dp[i][j][1]代表机器人从起点到达点(i, j)时方向为下的最小修改次数，则dp[i][j][0]可通过dp[i][j - 1][0]和dp[i][j - 1][1]计算得到，dp[i][j][1]可通过dp[i - 1][j][0]和dp[i - 1][j][1]计算得到，算法思路如下：

  1. 初始化dp[0][0][0]和dp[0][0][1]
  2. 边界处理，在最后一行的下一行加墙，在最后一列的下一列加墙
  3. 初始化数组dp的第一行和第一列
  4. 递推求解
  5. 输出min(dp[N - 1][M - 1][0], dp[N - 1][M - 1][1])
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
#include <iostream>
#include <cmath>

using namespace std;

char maze[110][110];
int dp[110][110][2];

int main()
{
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i ++) {
        for (int j = 0; j < M; j ++) {
            cin >> maze[i][j];
        }
    }
    dp[0][0][0] = (maze[0][0] == 'b');
    dp[0][0][1] = (maze[0][0] == 'b') + (maze[0][1] != 'b');

    //边界处理
    for(int i = 0; i < N; i ++) {
        maze[i][M] = 'b';
    }
    for(int i = 0; i < M; i ++) {
        maze[N][i] = 'b';
    }
    //初始化第一行，第一列
    int tmp = 0;
    for(int i = 1; i < M; i++) {
        if (maze[0][i] == 'b')
            tmp ++;
        dp[0][i][0] = tmp;
        dp[0][i][1] = tmp + (maze[0][i + 1] != 'b');
    }
    tmp = (maze[0][1] != 'b');
    for(int i = 1; i < N; i++) {
        if (maze[i][0] == 'b')
            tmp ++;
        dp[i][0][0] = tmp + (maze[i + 1][0] != 'b');
        dp[i][0][1] = tmp;
    }

    for(int i = 1; i < N; i ++) {
        for(int j = 1; j < M; j ++) {
            dp[i][j][0] = min(dp[i][j - 1][0] + (maze[i][j] == 'b'), dp[i][j - 1][1] + (maze[i + 1][j - 1] != 'b') + (maze[i][j] == 'b'));
            dp[i][j][1] = min(dp[i - 1][j][0] + (maze[i - 1] [j + 1] != 'b')+ (maze[i][j] == 'b'), dp[i - 1][j][1] + (maze[i][j] == 'b'));
        }
    }

    cout << min(dp[N - 1][M - 1][0], dp[N - 1][M - 1][1]);


    return 0;
}