UTS Open '18 P5 - Room 666

View as PDF

Submit solution

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

Problem type

Some UTS students want to sneak in to the mythical Room 666, where it is rumoured that the report cards are kept. However, the teachers have devised a 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

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!


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


Sample Output 1

2 4
6 6
4 3

Explanation for Sample Output 1

Here is one possible sequence of flips:

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

Sample Input 2


Sample Output 2

1 1
2 2


There are no comments at the moment.