UTS Open '18 P5 - Room 666

View as PDF

Submit solution



Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:

Problem type

Some UTS students want to sneak in to the mythical Room 666, where it is rumored that the report cards are kept. However, the teachers have devised an complex lock system to prevent students from opening the door. The lock consists of many switches arranged in a diamond shape like this:

Sample Input 1

Sample Input 1

Some switches are set to open (0), while others are set to closed (1). In order to unlock the door, all switches must be set to open. The students can flip any switch they want (changing its value from 0 to 1, or from 1 to 0), and they can do this at most 10^6 times. However, when a switch is flipped, all switches in the same row or column get flipped too. The students are puzzled by this elaborate contraption, so they ask you to unlock it! For the sake of these students' grades, help them find a sequence of flips that will unlock the door.

Input Specification

The first line contains the even integer N (1 \le N \le 1000), the height and width of the diamond-shaped lock. The next N lines contain N characters each: either a 0 (an open switch), 1 (closed switch), or . (no switch).

Output Specification

Output any sequence of flips that will unlock the door as follows: on the first line, print M (0 \le M \le 10^6), the number of flips in your sequence. On the next M lines, print two integers r, c (1 \le r, c \le n), indicating that the switch in row r, column c should be flipped (along with the other switches in row r or column c). The rows and columns are 1-indexed, with the top-left position being (1, 1) and the bottom-right position being (n, n). It is guaranteed that such a sequence exists - otherwise, even the teachers wouldn't be able to enter the room!

Subtasks

Subtask 1 [10%]

1 \le N \le 4

Subtask 2 [40%]

1 \le N \le 80

Subtask 3 [50%]

1 \le N \le 1000

Sample Input 1

8
...10...
..0110..
.011010.
11101011
00110100
.100111.
..1101..
...10...

Sample Output 1

3
2 4
6 6
4 3

Explanation for Sample Output 1

Here is one possible sequence of flips:

Move 1 Move 2 Move 3 Solved

Note that there are multiple solutions, and any solution that requires 10^6 flips or less will be accepted.

Sample Input 2

2
10
01

Sample Output 2

2
1 1
2 2

Comments

There are no comments at the moment.