hiho一下第150周《Demo Day》题目分析

14
1

作为一名身经百战的选手，相信这种“从左上到右下，只能向右和向下”的题目大家一定见得多了。这题一眼看去就散发出浓浓的DP气息。

第一个想法就是用f[i][j]表示从左上角到达(i, j)这个位置最少需要改变几个格子。不过仔细一想会发现由于这题限制只能在“撞墙”的时候换方向，所以不知道当前方向的话，是没有办法转移的。

于是我们可以把方向也加入状态中：用f[i][j][d]表示从左上角到达(i, j)这个位置，并且当前移动方向是d(d有两个取值，向上或向下)最少需要改变几个格子。

之后我们需要检视一下有没有后效性。也就是说如果一个格子(是否有障碍)会影响从左上角到(i, j)，那么这个格子会不会还影响到从(i, j)到右下角？ 简单分析一下，我们就会发现并不会有这样的情况出现。

最后我们要写出转移方程。假设我们现在要求f[i][j][右]的值，显然f[i][j][右]只可能从f[i-1][j][右]、f[i-1][j][下]、f[i][j-1][右]和f[i][j-1][下]转移而来。

我们以f[i-1][j][右]为例。我们到绿色格子(i-1, j)时方向是向右，为了到蓝色格子(i, j)是方向也是向右，我们需要两个黄色格子(i-1,j+1)和(i+1,j)是有障碍物的，同时(i, j)不能有障碍物。

所以此时f[i][j][右] = f[i-1][j][右] + (g[i][j] != 空) + (g[i-1][j+1] != 障碍物) + (g[i+1][j] != 障碍物)。(真是1,假是0)

当然f[i][j][右]还可能从f[i-1][j][下]、f[i][j-1][右]和f[i][j-1][下]转移而来。最终f[i][j][右]是取这四种情况的最小值。

总复杂度是O(NM)的。

1 answer(s)

0

一开始以为是图论,辛辛苦苦从50/100改到80/100.....

后来感觉不太对,发现是DP,分分钟就出来了........

N, M = map(int,raw_input().strip().split(' '))
maze = []
for i in range(N):
    line = raw_input().strip()
    maze.append(line)
ans = dict()
# posX poxY Direc0-1 0-right 1-down
ans[(0,0,0)] = 0
def hasblock(x, y):
    if x<0 or x>=N or y<0 or y>=M or maze[x][y] == 'b':
        return 1
    return 0

for i in range(N):
    for j in range(M):
        if j>0:
            ans[(i,j,0)] = min(ans.get((i,j-1,0),500), ans.get((i,j-1,1),500)+ 1- hasblock(i+1,j-1)  ) + hasblock(i, j)
        if i>0:
            ans[(i,j,1)] = min(ans.get((i-1,j,1),500), ans.get((i-1,j,0),500)+ 1- hasblock(i-1,j+1)  ) + hasblock(i, j)
print min( ans.get((N-1,M-1,0),500), ans.get((N-1,M-1,1),500) )

write answer 切换为英文 切换为中文

转发分享

▲