题目大意
已知手机键盘为
1 2 3
4 5 6
7 8 9
0
我们采用一种特殊的方式在手机上输入数字，即当按下一个键之后，只能把手指向下或者向右移动。开始时手指默认放在1上。
比如按下2之后，就不能再回到1这个按键。
问对于给定的数字S，能够通过这种特殊方式输入的最大不超过S的数字是多少。
解题思路
我们考虑如何模拟输入数字的过程：
从高位到低位，一位一位输入数字。
在已知S的前提下，我们要使得打出的数字尽可能接近S。则最好的方法就是从高位到低位，每一位都输入和S相同的数字。
先不考虑按键限制的情况下，可以写出一个函数：
dfs(depth):
If depth >= length Then
// 找到一个合法解
// 由于我们总是从高到低对数字进行枚举，因此第一个找到的解一定是最大解
Output(result)
Return True
End If
For i = 9 .. 0
If (i <= S[depth]) Then
result[depth] = i
If (dfs(depth+1)) Then
Return True
End If
End If
End For
Return False
接下来考虑如何按键限制条件。
当我们输入一个数字后，只能再输入键盘上在其右边或下边的数字。由此我们可以得到一个转移矩阵g[10][10]。
g[i][j]表示按下数字i后能否移动到数字j。若能够g[i][j]=true，否则g[i][j]=false。
比如：
g[1][2] = true,g[2][1] = false
当我们输入了前一位之后，后一位可以使用哪些数字也就确定了，所以我们再参数中增加最后一个输入的数字last。
在枚举数字时，我们也需要加入条件判断是否满足要求。
因此将函数改造为：
dfs(depth, last):
If depth >= length Then
// 找到一个合法解
// 由于我们总是从高到低对数字进行枚举，因此第一个找到的解一定是最大解
Output(result)
Return True
End If
For i = 9 .. 0
If (i <= S[depth] and go[last][i]) Then
result[depth] = i
If (dfs(depth+1, i)) Then
Return True
End If
End If
End For
Return False
但这个函数现在还是有问题的。
由于在该函数中，我们保证了每一位数字一定小于等于S的对应位。
比如当S=300时，用我们这个函数找出的最优解是200，而实际上可以打出299这个数字。
也就是说，当满足某一个条件后，最优解某些数位上的数字是可能大于S对应位的。
这个条件是：当答案的其中一位已经小于S的对应位时，这一位之后的数位可以选择任意一个数字。
为了保证答案尽可能大，因此在后面的数位上我们要选择能够移动到的最大数字。
再一次改进后的函数为：
dfs(depth, last, below):
If depth >= length Then
// 找到一个合法解
// 由于我们总是从高到低对数字进行枚举，因此第一个找到的解一定是最大解
Output(result)
Return True
End If
If below == True Then
// 已经有高位小于S的对应位置
//将后面的数位填充为last能够移动到的最大数字
result[depth..length-1] = max{i|go[last][i]==true}
Output(result)
Return True
End If
For i = 9 .. 0
If (i <= S[depth] and go[last][i]) Then
result[depth] = i
If (dfs(depth+1, i, i < S[depth])) Then
Return True
End If
End If
End For
Return False
到此，给出的dfs函数即可通过所有的测试点。
由于本题仍然是多组输入数据，所以一定要记得初始化。
“如果高位t已经小于s ，补9” 这里不见得一定补9。