#P2262. *【最短路+DP】矩阵逃离
*【最短路+DP】矩阵逃离
【题意】
一个 行 列的矩阵,由 格子组成,有的格子里有障碍物。
从矩阵的 出发到 ,每一步可以往上下左右四个方向移动一格,但不能移动经过有障碍物的格子,除非动用一次技能移除障碍物。
求最多移除 个障碍物的情况下,请问走到 最少需要多少步?
【输入格式】
第一行三个正整数 。
下来 行每行 个字符代表矩阵的情况,空格子用 0 表示,有障碍物的格子用 1 表示,保证和无障碍物。
【输出格式】
输出一个整数,表示最少步数。
若无法到达 ,请输出No Answer。
【样例1 输入】
5 5 1
00111
01000
00010
01010
01100
【样例1 输出】
8
【样例2 输入】
3 3 1
010
111
010
【样例2 输出】
No Answer
【数据范围】
| 测试点编号 | ||
|---|---|---|