3282: 飙车
题目描述
已知公路总长L米,一共有K个赛道,你的赛车总是和公路上其他的普通的车走相反的方向,并且所有的车每秒沿赛道行驶1m(具体看图)
(宇宙新秀:我的Evo IV怎么这么烂….).问题是:跑到终点最少撞多少次车?我们简化一下模型,画一个(L+1)*K的网格,设所有的车都是点,并且每秒末都会出现在这个网格的某个顶点上.公路上其他的车都以固定的1m/s的速度自上而下行驶,而你的跑车自下而上行驶,并且每秒可以从一个点行驶到它上方\左上方\右上方的点(假设飘移不浪费时间,具体请看图).我们假设,撞车不会使车损坏,不会使车减速(宇宙新秀:我的Evo IV怎么这么强~~)对于撞车的设定:当每秒末你的车和另外一辆车处在同一点上时,算撞车;你的车和另一辆车迎面开过来,算撞车.具体请看下图: 假设一开始你可以选择任意一个赛道开始比赛,要求你写一个程序,计算到达终点至少要撞多少次车。对于上边的例子,只要开始选择第三赛道开始跑,然后一路向北,就可以不撞车而到达终点。
输入
首行两个数,L,K,表示赛道距离,以及有几个赛道.接下来L行,每行K个字符,第i行第j个字符表示公路距终点距离为i-1的第j个赛道的初始状态:0表示该点没有车,1表示该点有车.铭记一点:初始时你的车在第L+1行,你可以指定一个第L+1行的位置为你的车的初始位置,而第L+1行是不在输入文件里的.
输出
一个数ans,表示最少撞车次数
样例输入 复制
4 4
1000
0100
0001
0000样例输出 复制
0提示
【输入样例2】6 4111111111111000011110000【输出样例2】3【对样例2的说明】初始 第一秒 第二秒 第三秒距终点0m 1111 距终点1m 1111 1111距终点2m 1111 1111 1111距终点3m 0000 1111 1111 1P11距终点4m 1111 0000 P111 1111距终点5m 0000 P111 0000 1111距终点6m CC代表该点只有你的车,P代表该点既有你的车又有其他的车.最优方案为第一秒直走,与一辆车相撞,第二秒直走,又与一辆车相撞,第三秒斜向右走,又与一辆车相撞,总共三次.如果第三秒直走,将与两辆车相撞,那么就撞了四次,所以三次最优.【输入样例3】4 41111111111111111【输出样例3】2【对样例3的说明】不停地斜着走【数据规模】1<=n<=100,1<=k<=10【说明】：此题中出现的所有数字均为整数