Erasing Matrix
Time limit1sMemory limit256 MB
Decide whether all cells of a grid can be driven to zero by repeatedly adding the same integer k to two adjacent cells while keeping every value non-negative, and print a valid sequence of at most 10^6 operations.
- Level
Hard8 of 10
- Topics
- Graph, Greedy, Implementation, Math
- Solved
- No attempts yet
Problem
Gyu-min has an N x M grid, and each cell contains a non-negative integer.
Gyu-min wants to make every integer in the grid equal to 0. To do this, he may perform the following operation.
- Operation: choose two adjacent cells in the grid, and choose an integer k. Add k to the numbers in the two adjacent cells.
After each operation, every number in the grid must still be a non-negative integer. Two cells are 'adjacent' if they share a side.
Given the N x M grid Gyu-min has, determine whether he can reach the goal using these operations.
Input
The first line gives the grid's height N and width M. (2 ≤ N, M ≤ 500)
From the second line to the N+1-th line, the numbers in Gyu-min's grid are given, M per line.
Each integer given is a non-negative integer no greater than 10^6.
Output
If Gyu-min cannot reach the goal, print -1.
If Gyu-min can reach the goal, print a way to reach it in the format below.
The first line gives the number of operations X. It must satisfy 0 ≤ X ≤ 10^6.
From the second line to the X+1-th line, line i gives information about the (i-1)-th operation Gyu-min performs, in the form r1 c1 r2 c2 k.
Here (r1, c1) and (r2, c2) are the coordinates of the two adjacent cells Gyu-min chose, satisfying 1 ≤ r1, r2 ≤ N, 1 ≤ c1, c2 ≤ M, and |r1-r2|+|c1-c2|=1.
Also, k is the integer Gyu-min adds to the numbers in the two cells, and it must satisfy -10^12 ≤ k ≤ 10^12.
Note that the number of operations does not need to be minimized.
Also, if Gyu-min can reach the goal, it is guaranteed that he can reach it with a method satisfying the given output conditions.