A7554. [ABC146F] Sugoroku
编程题
普及+/提高
知识点
题目描述
高桥君在玩双六棋，棋盘格由用$0$到$N$编号的共$N+1$个格子构成。每一回合，高桥君会扔一个点数$1$到$M$的骰子。如果高桥君当前在第$i$格，骰子扔出$k$点，高桥君就前进到第$i+k$格。 如果此时$i+k > N$，高桥君立刻输掉。另外，棋盘上还有若干个“GameOver格”，如果高桥停在这些格子，也立刻输掉游戏。
假设高桥君可以自由控制骰子的点数，那么他从$0$号格子出发，到达$N$号格子，最短需要多少回合？输出用最短回合到达$N$格时，每回合骰子的点数组成的序列；如果无法到达$N$号格子，输出-1。
假设高桥君可以自由控制骰子的点数，那么他从$0$号格子出发，到达$N$号格子，最短需要多少回合？输出用最短回合到达$N$格时，每回合骰子的点数组成的序列；如果无法到达$N$号格子，输出-1。
输入格式
第1行，两个正整数$N,M$
第2行，一个长为$N+1$的字符串$S$。$S_i=0$表示第$i$格是一个普通格子；$S_i=1$表示第$i$格是一个GameOver格。
第2行，一个长为$N+1$的字符串$S$。$S_i=0$表示第$i$格是一个普通格子；$S_i=1$表示第$i$格是一个GameOver格。
输出格式
输出用最短回合到达$N$格时，每回合骰子的点数组成的序列，若有多种序列回合数都是最短，输出其中字典序最小的。
如果无法到达$N$号格子，输出-1。
如果无法到达$N$号格子，输出-1。
输入输出样例
输入 #1
9 3 0001000100
输出 #1
1 3 2 3
输入 #2
5 4 011110
输出 #2
-1
输入 #3
6 6 0101010
输出 #3
6
说明/提示
按$1,3,2,3$的顺序扔出骰子的点数，高桥君会经过第$1,4,6$格最终到达第$9$格。
无法在$3$次以内到达第$9$格。$1,3,2,3$是所有$4$次到达第$9$格的点数序列中，字典序最小的。
$1 \le N \le 10^5$
$1 \le M \le 10^5$
$S$长度为$N+1$，只由字符'0'和'1'组成，保证$S_0=0$，$S_N=0$。
无法在$3$次以内到达第$9$格。$1,3,2,3$是所有$4$次到达第$9$格的点数序列中，字典序最小的。
$1 \le N \le 10^5$
$1 \le M \le 10^5$
$S$长度为$N+1$，只由字符'0'和'1'组成，保证$S_0=0$，$S_N=0$。