ZOJ Problem Set - 3477
Akasim Matrix is the most powerful grid computing platform developed by Academy City. Each node is identified by its serial number -- a 2-tuple (x, y). The node with serial number (x, y) can communicate with its neighbors, namely (x - 1, y), (x + 1, y), (x, y - 1) and (x, y + 1), if exists. The Akasim Matrix is made up of n * m nodes whose serial numbers vary from (1, 1) to (n, m).
Recently, some magical girls attacked the Akasim Matrix. They injected an extremely infectious virus called soldier of love into the node (xi, yi) at day di. The virus spread very fast, every day, an infected node will make all its neighbors infected. The soldier of love will devastate the Akasim Matrix once it infects all nodes. Academy City has very advanced technologies in anti-virus as well as many other principles of science. They can clear all virus as long as they successfully build an anti-virus program at any node before it's infected. But this process does cost a long long time. So they want to know how many days they have at most and which node they should build the anti-virus program at.
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
Each test case starts with three integers 1 ≤ n ≤ 220, 1 ≤ m ≤ 219 and 1 ≤ v ≤ 218. Then v lines, the i-th line contains three integers 1 ≤ xi ≤ n, 1 ≤ yi ≤ m and 0 ≤ di < 1,000,000,000. Each test case ends with a blank line.
For each test case, output "d (x, y)". In case that more than one nodes are infected at the d-th day, you should first minimize the x, then minimize the y.
3 3 3 1 2 2 1 3 3 1 3 3 1 3 3 4 1 1 1 1 3 1 3 1 1 3 3 1
3 (1, 1) 5 (1, 1) 3 (2, 2)
Author: WU, Zejun
Contest: The 11th Zhejiang University Programming Contest