题目
backgrounds
夕阳镇第五幼儿园的zhangzj被他的好♂友带进了puzzle game 的坑,其中他最感兴趣的是netgame,$1 \times 1$的格子他一眼秒,但由于幼儿园有上机时间限制,所以他想很快找出最优解,但是他忙着找更多的好♂友,只好请你来帮忙。
content
有一个$n \times m$的网格,除了最左边一列和最右边一列,每个格子上有一些管道,需要通过旋转一些格子使得最右边一列上的一些格子能够通过管道与至少一个最左边一列的格子连通。每个格子上的管道都是由一个中间管道扩展到四个方向中的若干个,也就是说,这个格子的四个方向上如果有管道,那么这些方向是联通的。例如上方、左方和右方有管道,那么这三个方向的格子如果有朝向这个格子的管道,就可以通过这个格子上的管道连通。
比如这样:
问最右边一列的格子最多有几个同时与最左边一列的格子连通。
input format
多组数据。
对于每组数据,第一行有两个整数$n$和$m$,为网格图的行数和列数。
下接$n$行,每行$m-2$个整数$x_{i,j}$,表示网格图第$i$行第$j+1$列的管道,如果$x_{i,j}\ {\rm and}\ 1 = 1$,那么向上有管道,如果$x_{i,j}\ {\rm and}\ 2 = 2$,那么向右有管道,如果$x_{i,j}\ {\rm and}\ 4 = 4$,那么向下有管道,如果$x_{i,j}\ {\rm and}\ 8 = 8$,那么向左有管道。
output format
若干行,每行一个数,表示一组数据的答案。
sample input
1 3
5
sample output
1
sample explanation
将中间的格子旋转成向左和向右连通即可。
constraints
对于$20\%$的数据,$n \times (m - 2) \leq 8$。
对于另外$10\%$的数据,$n = 1$。
对于另外$10\%$的数据,$m = 3$。
对于$100\%$的数据,$1 \leq n \leq 9$,$3 \leq m \leq 20$,数据组数在$5$以内。
数据有梯度,大家可以尽情骗分。