我们称一个长度为 的字符串为扫雷字符串,当且仅当它满足以下条件:
- 每个字符要么是
*(表示一颗地雷),要么是数字 0、1 或 2。
- 每个数字字符的值必须等于与其相邻的地雷数量(相邻是指在字符串中左右相邻的位置)。
例如,当 时:
0000000 是一个合法的扫雷字符串,没有地雷。
******* 是一个合法的扫雷字符串,全是地雷。
0001*2* 是一个合法的扫雷字符串,有两颗地雷。
0001000 不是一个合法的扫雷字符串,因为中间的 1 相邻的地雷数量不是 。
**0001* 不是一个合法的扫雷字符串,因为最左边的 0 相邻的地雷数量不是 。
2*1*02* 不是一个合法的扫雷字符串,所有数字都错误。
现在,我们将所有合法的扫雷字符串按照字典序从小到大排序(依据字符的 ASCII 码值进行排序),并从 开始编号。
给定字符串长度 和一个非负整数 ,请找出在这个排序中排在第 位的扫雷字符串。如果不存在编号为 的字符串(即 大于等于总数),则返回一个空字符串。