#-【MYOI入团赛】铁山靠nn##-题目背景nnKUN-被成千上万的-IKUN-拥到了操场上……nn##-题目描述nnIKUN-们要求-KUN-和他们来一场比赛。把操场想象成一个-$ntimes-m$-的矩阵KUN-站在-$11$篮筐在-$nm$。KUN-只能向右或下移动。如果-$ij$-号位上的数为-$1$那表示该位置有人KUN-过不去否则可以过去。当-KUN-到达-$nm$-时他就赢了。nn已知-KUN-每一秒都有以下两种选择：nn--移动：耗费-$1S$-。nn--铁山靠：把他右或下位置

题目描述

IKUN 们要求 KUN 和他们来一场比赛。把操场想象成一个 n×m 的矩阵，KUN 站在 (1,1)，篮筐在 (n,m)。KUN 只能向右或下移动。如果 (i,j) 号位上的数为 1，那表示该位置有人，KUN 过不去，否则可以过去。当 KUN 到达 (n,m) 时他就赢了。

已知 KUN 每一秒都有以下两种选择：

移动：耗费 1S 。

铁山靠：把他右或下位置上的人撞翻，并站到该位置。耗费 3S。为了保证 IKUN 们的安全，KUN 最多用 k 次该技能。

几乎所有 IKUN 都来到了篮球场想和 KUN 一决雌雄，可是 KUN 在唱《只因你太美》，他们全笑得动不了了！

KUN 不想浪费时间。现在，他想知道自己最少耗费多少时间才可以赢得比赛。如果赢不了，输出 No way。

输入格式

输入一共 n+1 行。

第一行输入三个整数 n,m,k，表示篮球场的大小为 n×m，KUN 最多使用技能 k 次。

接下来 n 行，每行 m 个整数，表示矩阵 a，1 表示该位置上有人，否则表示没人。

输出格式

一个整数 ans，输出 KUN 赢得比赛需要的最短时间。如果赢不了，输出 No way。

样例输入#1

3 3 1 0 1 1 1 0 1 0 0 0

样例输出#1

6

样例输入#2

4 4 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0

样例输出#2

No way

样例输入#3

见附件中的bump3.in文件

样例输出#3

见附件中的bump3.out文件

题解

因为美丽的图论太难了，所以我想到了搜索。

我们可以把靠过去的点标为1，没有靠过去的标为0；

这时我们就可以搜索了，但是有k次靠的机会，我们就需要记录当前的靠的机会数，所以我们可以记录当前的状态。

状态有这些：

当前点 $(x,y)$

剩余靠的次数 $t$

时间 $time$

我们可以用记忆化搜索，把状态记录下来，也就是把状态压缩一下，然后记录答案。

记忆化搜索过程：

当前点为 $(x,y)$，剩余靠的机会为 $t$，时间为 $time$。

先处理边界：

如果 $x=n$，$y=m$，就返回 $time$；

如果 $t=0$，就不能靠过去，只能移动。如果当前点为1，就返回 $inf$，否则返回 $dfs(x+1,y,t,time+1)$ 或者 $dfs(x,y+1,t,time+1)$ 的最小值。

如果 $t>0$，就可以选择靠过去或者移动。如果当前点为1，就返回 $dfs(x+1,y,t,time)$ 或者 $dfs(x,y+1,t,time)$ 的最小值。否则就返回 $dfs(x+1,y,t,time+1)$ 或者 $dfs(x,y+1,t,time+1)$ 或者 $dfs(x+1,y,t-1,time+3)$ 或者 $dfs(x,y+1,t-1,time+3)$ 的最小值。

注意如果 $ans=inf$ 就输出 No way。

C++ 代码