Problem I
Switch Grid
Input: Standard Input
Output: Standard Output
There is a grid with N rows and M columns. The rows are numbered from 0 to N-1 and columns are numbered from 0 to M-1. Each of the cell in row 0 and each of the cell in column 0 contains a bulb. Except the cell in row 0 and column 0 is empty. All the other rows can contain a switch. The switch in the cell on row r and column c change the states of both bulbs in row r and column c. You are given the initial states and the desired states of each of the bulb. Now given a list of switches you need to press them in such a way that all the bulbs change their states from their initial to desired states.
Input
Input contains multiple test cases.
First line contains T the number of test cases.
Each of the test case consists of 7 lines.
1. 3 space
separated integers N(1≤N≤1000),M(1≤(1≤N≤1000)≤1000)
and S(1≤S≤4000). N is the number of rows in the grid, M is the
number of columns in the grid and S is the number of switches.
2. N-1
space separated integers. Each of these
integers is either 0 or 1.The i’th (i starts from 1) denotes the initial state of the bulb in (i,0). 0 means off and 1 means on.
3. N-1
space separated integers. Each of these
integers is either 0 or 1. The i’th (i starts from 1) denotes the final state of the bulb in (i,0).
4. M-1
space separated integers. Each of these integers is either 0 or 1. The i’th (i starts from 1) denotes
the initial state of the bulb in (0,i).
5. M-1
space separated integers. Each of these integers is either 0 or 1. The i’th (i starts from 1) denotes
the final state of the bulb in (0,i).
6. S space
separated integers. Each of these
integers is between 1 and N-1 inclusive. The i’th (i starts from 0) integers denote the row number of the i’th switch.
7. S space
separated integers. Each of these
integers is between 1 and M-1 inclusive. The i’th (i starts from 0) integers denote the column number of the i’th switch.
There is a blank
line after each of the test case. There will be 100 test cases.
Output
For each test case output contains a single line. When there is no way
to transform the state of all the bulbs the line contains -1. Otherwise the
line starts with X followed by X integers. X is the number of switch presses
required to transform all the bulbs into the desired states. X should be less
than 10000.The next X integers denotes the indices of the switches that need to
be pressed. All of these X integers should be distinct. Any combination of
switch presses that transforms all the bulbs to their desired state will be
considered correct.
|
3 3
3 2 0
0 1
0 0
0 0
1 1
2 1
2 3
3 3 0
0 1
1 0
0 1
1 1
1 2 1
2 2 4
4 5 0
0 0 0
1 1 0
0 0 1
0 1 1
1 2 2 3 1
3 1 2 2 |
-1 2
0 2 4
0 1 3 4 |
Problemsetter: Abdullah al Mahmud
Special Thanks: Manzurur Rahman Khan