题面：http://hihocoder.com/problemset/problem/1290
2016微软校招笔试第三题
题意
给定一个迷宫，起点为左上角，终点为右下角。’.’表示能走, ‘b’表示不能走。
现在走迷宫时每次只能向右或是向下，且在没有碰到阻碍时不能停下来。
一开始是向右走的。
这种走法可能会导致走不到出口。
所以现在你可以改变迷宫的某一些格子，即可以让能走的位置变成不能走。
也可以让不能走的位置变成能走。
求最少需要调整几个格子。
解法
这个题肯定是dp了。
问题是怎么构建状态及转移方程。
一开始自己想的是$dp[i][j]$表示正好到达$(i,j)$位置时所需要最小的格子变化个数。
写了半天连第一行第一列的初始值都没写出来。
然后就只能看看别人的题解看看怎么写了。
由于可以向右或是向下走，所以到达每个格子时应该会有两种方向。
分别是向右和向下。
由于需要走到某个位置，所以我们只需要看会不会经过这个点即可。
不用判断正好到达（即前方有阻碍）
状态为：$Up[i][j], Left[i][j]$分别表示到达$(i,j)$时一个是向下走，一个是向右走的。
那么我们发现，要计算到达一个位置的最小变化格子个数，可能是从正上方的转移，也可能是从左侧转移。
状态转移方程如下：
画个图就不难理解了。考虑方向的转变就需要增加一个障碍物。
有一个小技巧，感觉还是挺有用的。
这边就是把周围一圈的点都设成障碍物，这样就不用判断边界条件了。
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
const int maxn = 1e2 + 10;
const int inf = 0x7f7f7f7f;
char s[maxn][maxn];
int Up[maxn][maxn], Left[maxn][maxn];
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++)
{
cin >> s[i];
s[i][m] = 'b';
}
for(int i = 0; i <= m; i++)
s[n][i] = 'b';
Left[0][0] = Up[0][0] = (s[0][0] == 'b');
for(int i = 1; i < m; i++)//初始化第一行
{
Up[0][i] = inf;
Left[0][i] = Left[0][i - 1] + (s[0][i] == 'b');
}
Up[1][0] = (s[0][1] == '.');
Left[1][0] = inf;
for(int i = 2; i < n; i++)//初始化第一列
{
Left[i][0] = inf;
Up[i][0] = Up[i - 1][0] + (s[i][0] == 'b');
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
Left[i][j] = min(Left[i][j - 1], Up[i][j - 1] + (s[i + 1][j - 1] == '.')) + (s[i][j] == 'b');
Up[i][j] = min(Up[i - 1][j] , Left[i - 1][j] + (s[i - 1][j + 1] == '.'))+ (s[i][j] == 'b');
}
}
cout << min(Left[n - 1][m - 1], Up[n - 1][m - 1]) << endl;
return 0;
}