1462: PIPI的弹珠箱子
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 670 Solved: 318
[Submit] [Status] [Web Board] [Creator:]
Description
PIPI在回寝室的路上捡到了一个箱子，箱子的顶部和底部都是开着的，箱子内部可以看成一个n*m的二维网格。
箱子内部的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将弹珠导向左侧或者右侧。
将弹珠导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将弹珠导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
在箱子每一列的顶端各放一颗弹珠。每颗弹珠都可能卡在箱子里或从底部掉出来。如果弹珠恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。
现在PIPI想知道从顶部每一列放入的弹珠会从底部哪一列出来？
箱子内部的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将弹珠导向左侧或者右侧。
将弹珠导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将弹珠导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
在箱子每一列的顶端各放一颗弹珠。每颗弹珠都可能卡在箱子里或从底部掉出来。如果弹珠恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。
现在PIPI想知道从顶部每一列放入的弹珠会从底部哪一列出来？
Input
第一行输入两个整数n,m，分别表示箱子的行数和列数，1<=n,m<=1000
接下来n行，每行m个整数，该整数只会等于-1或者1，表示每个格子对角线的方向
接下来n行，每行m个整数，该整数只会等于-1或者1，表示每个格子对角线的方向
Output
输出m个整数，分别表示从第1列到第m列放入的小球会从哪一列落下。如果中途被卡住输出-1。
Sample Input
5 5
1 1 1 -1 -1
1 1 1 -1 -1
-1 -1 -1 1 1
1 1 1 1 -1
-1 -1 -1 -1 -1
Sample Output
1 -1 -1 -1 -1