Readme

1293.Shortest-Path-in-a-Grid-with-Obstacles-Elimination

如果是不允许穿越障碍，那么我们用通常的BFS的做法，就可以记录到达每个位置(i,j)所需要的最短步数dp[i][j].但是现在允许穿越障碍，到达(i,j)的最短步数就要有所区分：

O X O O
O X O O
O O O O

在上面的例子中，如果不穿越障碍，从(0,0)到(0,2)需要6步；但是如果允许穿越障碍，那么只需要2步。那么到底选择哪个更好呢？答案是说不准。前者使用的elemination次数少（可以留着给之后的步骤用），后者的实际步数更少。所以这两种状态我们都要记录下来。因此我们使用dp[i][j][k]表示，从(0,0)走到(i,j)，并且使用了k次障碍消除，所需要的最短步数。

因为本题是允许上下左右移动，没有“无后效性”，所以dp[i][j][k]无法使用动态规划来转移，只能用BFS的暴力搜索来前进。比如，我们知道dp[i][j][k]=step，那么如果向右走一步到空地，就有dp[i][j+1][k]=step+1；但是特别注意，如果向右走一步是障碍的话，那么需要使用一次障碍消除，即dp[i][j+1][k+1]=step+1

直到我们第一次走到dp[m-1][n-1][k]，并且k不大于K的时候，dp值就是最少的步骤。如果BFS进行了K轮还没有走到右下角，那么说明无解。