
ZOJ Problem Set  4018
Given a grid with \(n\) rows and \(m\) columns, each cell may contain nothing or a cross consisting of three dotted segments and one solid segment. Let's denote the cell located on the \(i\)th row and the \(j\)th column by \((i, j)\). When you click on a cross, it will rotate 90 degrees clockwise, thus changing the direction the solid segment points to. Your goal is to click on some crosses in some proper order so that the solid segment of every cross points upwards. But beware, this task is harder than you think it may be. After the rotation of a cross in \((i,j)\) ends, the cross \((i',j')\) pointed by the solid segment of \((i,j)\) will also begin to rotate 90 degrees clockwise, and after the rotation of \((i',j')\) ends, another cross may be triggered if pointed by the solid segment of \((i',j')\)... This chain reaction comes to an end only when the solid segment of the previouslyrotated cross points to an empty cell or points out of the map. To help you understand, please check the following pictures showing a chain reaction on a grid with \(n = m = 3\) step by step.
Given a grid with \(n\) rows and \(m\) columns, please find out a proper order to click on the crosses so that the solid segment of every cross points upwards. You can perform at most 6000 clicks for each test case. InputThere are multiple test cases. The first line of the input contains an integer \(T\) (\(1 \le T \le 50\)), indicating the number of test cases. For each test case: The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10\)), indicating the size of the grid. For the following \(n\) lines, the \(i\)th line contains \(m\) integers \(t_{i,1}, t_{i,2}, \dots, t_{i,m}\) (\(1 \le t_{i,j} \le 3\)), where \(t_{i,j}\) indicates the initial state of the cross at intersection \((i, j)\).
OutputFor each test case, first output one line containing one integer \(k\) (\(0 \le k \le 6000\)), indicating the number of clicks. Then \(k\) lines follow. Each line contains two integers \(i, j\) (\(1 \le i \le n, 1 \le j \le m\)) separated by a space, indicating that you click on the cross in cell \((i, j)\). If there's no way to make the solid segment of every cross point upwards in 6000 clicks, just output "1" (without quotes) instead. Sample Input2 3 2 2 3 1 0 3 2 2 2 3 2 0 1 Sample Output8 1 1 1 2 1 2 2 2 2 2 3 1 3 1 3 2 5 1 1 2 1 2 1 2 1 1 2 HintWe've also prepared the following playable example with \(n = m = 4\). You can try it for further understanding. (If you cannot see this example, try Firefox) (Controls: Click to rotate, and refresh to restart) Author: YANG, Xinyu Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple 