微软2016校园招聘4月在线笔试 C. Demo Day 题解

#include <iostream>
using namespace std;

struct adjust_dt
{
    size_t right;
    size_t down;
};

size_t min_num(char maze[100][100], size_t N, size_t M)
{
    adjust_dt dp[100][100];

    dp[0][0].right = 0;
    if (maze[0][1] == 'b')
        dp[0][0].down = 0;
    else
        dp[0][0].down = 1;

    // 第一行
    for (size_t i = 1; i < M; ++i)
    {
        // right值由左侧点right值以及当前点类型决定
        if (maze[0][i] == 'b')
            dp[0][i].right = dp[0][i-1].right + 1;
        else
            dp[0][i].right = dp[0][i-1].right;

        // down值由当前right值和右侧点类型决定
        if (i + 1 == M || maze[0][i + 1] == 'b')
            dp[0][i].down = dp[0][i].right;
        else
            dp[0][i].down = dp[0][i].right + 1;
    }

    // 第二行
    for (size_t i = 1; i < N; ++i)
    {
        // down值由上侧点down值和当前点类型决定
        if (maze[i][0] == 'b')
            dp[i][0].down = dp[i-1][0].down + 1;
        else
            dp[i][0].down =  dp[i-1][0].down;

        // right值由当前down值和下侧点类型决定
        if (i + 1 == N || maze[i + 1][0] == 'b')
            dp[i][0].right = dp[i][0].down;
        else
            dp[i][0].right = dp[i][0].down + 1;
    }

    // 一行一行地来
    for (size_t i = 1; i < N; ++i)
    {
        for (size_t j = 1; j < M; ++j)
        {
            // 参考上侧点计算的right和down
            size_t right1, down1;

            // down由上侧点down和当前类型决定
            if (maze[i][j] == 'b')
                down1 = dp[i - 1][j].down + 1;
            else
                down1 = dp[i - 1][j].down;

            // right由上侧down和下侧点类型决定
            if (i + 1 == N || maze[i + 1][j] == 'b')
                right1 = down1;
            else
                right1 = down1 + 1;

            // 参考左侧点计算的right和down
            size_t right2, down2;

            // right由左侧right和当前类型决定
            if (maze[i][j] == 'b')
                right2 = dp[i][j-1].right + 1;
            else
                right2 = dp[i][j-1].right;

            // down由左侧right和右侧类型决定
            if (j+1 == M || maze[i][j+1] == 'b')
                down2 = right2;
            else
                down2 = right2 + 1;

            // 综合以上计算结果
            dp[i][j].down = min(down1, down2);
            dp[i][j].right = min(right1,right2);
        }
    }

    return min(dp[N - 1][M - 1].right, dp[N - 1][M - 1].down);
}

int main()
{
    size_t N, M;
    std::cin >> N >> M;
    char maze[100][100];
    for (size_t i = 0; i < N; ++i)
        for (size_t j = 0; j < M; ++j)
            std::cin >> maze[i][j];
    std::cout << min_num(maze, N, M) << endl;
    return 0;
}