Problem E
Secret Walk

cc by-s

In the exotic and warm city of Mänhettan live Harry and his absent-minded friend Tobias. The city is an $N \times N$ grid with coordinates $(x,y)$ where $0 \le x,y < N$. There is a house on every cell where both $x$ and $y$ are odd. The top-left cell is $(0,0)$, the bottom-left cell is $(N-1,0)$, and the bottom-right cell is $(N-1,N-1)$.

Tobias lives in one of these houses, and his school is in another. They are not on the same row or column, because Harry has visited Tobias and could not see the school through the window.

Tobias may move between two cells that share a side; each such move takes exactly one minute. Every day he walks along a shortest path to school and sends messages like “On my way now!” and “Just arrived!”, which means Harry knows exactly how long it takes Tobias to go from his house to the school.

Although Harry has visited Tobias and knows whether a cell is a house, he has forgotten both where Tobias lives and where the school is located.

To figure this out, each day Harry may magically create walls on any cells that do not contain houses. That day it takes $t$ minutes for Tobias to travel from his house to the school, or $t=-1$ if he gets completely stuck. After the day ends, all walls Harry created disappear.

Your task is to help Harry determine which house Tobias lives in and which house the school is in, using as few days as possible. Harry may use up to 365 days, but you get more points the fewer days you use.

Interaction

This is an interactive problem.

• Your program must first read one line containing an integer $N$ $(5 \le N \le 75,$ $N$ is odd$)$, the height and width of the grid. Then it reads $N$ lines, each with $N$ characters describing the grid. The character H means that cell is occupied by a house, while . means it is empty.

• Then your program interacts with the grader. To learn the number of minutes $t$ Tobias needs when taking a shortest path, you can issue a query by placing walls. Do this by printing a line containing a question mark ?. On the following $N$ lines print an $N \times N$ grid that is a copy of the input grid with any subset of empty cells . replaced by # (walls).

  Then read an integer $t$ ($-1 \le t \le N^2$), the minimum number of minutes Tobias needs to travel from his house to the school if he may pass through houses (H) and empty cells (.), but not walls (#).

• When you want to output your final answer, print a line starting with an exclamation mark ! followed by four integers $x_1\ y_1\ x_2\ y_2$ where $(x_1,y_1)$ and $(x_2,y_2)$ are the coordinates of Tobias’s house and the school in any order. The format must be ! x1 y1 x2 y2. For your answer to be accepted, either Tobias’s house is $(x_1,y_1)$ and the school is $(x_2,y_2)$, or vice versa.

  After this your program should terminate.

The grader is non-adaptive: the positions of Tobias’s house and the school are fixed before interaction starts.

Make sure to flush your output after every query, otherwise you may get Time Limit Exceeded. In Python this happens automatically as long as you use input() to read lines. In C++ cout << endl; flushes, but you can also use cout << flush; or fflush(stdout);, and in Java System.out.flush();.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

In the last test group your score depends on the number of days used according to:

Here $Q$ is the maximum number of days used on any test case. The score is rounded to the nearest integer.

To get full points in this group, Harry must solve every test case in at most $5$ days.

Below is a table of scores for selected $Q$ values:

Further down the page there is a file points.txt containing the score for every possible $Q$. There is also a testing_tool.py you can use to test your solution locally.

5
.....
.H.H.
.....
.H.H.
.....

?
.....
.H#H.
.###.
.H#H.
.....

8

?
..#..
.H#H.
#..##
.H#H.
..#..

-1

! 1 1 3 3

9
.........
.H.H.H.H.
.........
.H.H.H.H.
.........
.H.H.H.H.
.........
.H.H.H.H.
.........

?
#...##..#
.H#H#H#H.
.#######.
.H#H.H#H.
..#.#..#.
.H#H.H#H.
.###.###.
.H#H.H#H.
....#...#

14

?
.........
.H.H.H.H.
.........
.H.H.H.H.
.........
.H.H.H.H.
.........
.H.H.H.H.
.........

6

! 5 7 3 3