Escape the Maze: Map Reconstruction

This is an interactive problem. You are trapped inside a maze and your task is to deduce the entire map of the maze.

The maze is an \(n\times n\) grid where each cell is either an obstacle or a free path. An obstacle is denoted by 1 and a free path by 0. The cells are indexed from top to bottom and left to right such that the cell in the \(i\)th row and \(j\)th column is denoted by \((i,j)\).

Two cells are connected if and only if they share a common side (4-connected). It is guaranteed that there is exactly one connected block of 0's, and your starting position is inside this connected block.

The maze boundaries (first row, first column, last row, and last column) are all obstacles.

Implementation Details

You need to implement a function:

string find_out_map(int x, int y, int n)

Here, x and y denote your starting coordinates \((x,y)\) with \(1 < x,y < n\), and n is the size of the maze.

The returned string represents the maze map in row-major order. Specifically, the \(i\)th character (\(0\le i < n\times n\)) corresponds to the cell at row \(\lfloor\frac{i}{n}\rfloor+1\) and column \(i+1 - n\lfloor\frac{i}{n}\rfloor\). A character '1' indicates an obstacle at that cell, while '0' indicates a free path.

You are allowed to use the following function to explore the maze:

bool move_to(char position)

Here, position is one of the characters in 'W', 'A', 'S', 'D' which correspond to moving up, left, down, and right respectively. The function returns true (or 1) if the move was successful and false otherwise. Note that except at the very beginning, you cannot obtain your current coordinates from the interactive system. If an invalid move command is given, the behavior is undefined.

The maze is fixed (it does not change during execution) and your function may be called multiple times so ensure proper initialization if needed.

inputFormat

The input consists of three integers x, y, and n provided in a single line, where \(x\) and \(y\) are the starting coordinates and \(n\) is the size of the \(n\times n\) maze.

outputFormat

Output a single string of length \(n\times n\) representing the maze. The \(i\)th character corresponds to the cell at row \(\lfloor\frac{i}{n}\rfloor+1\) and column \(i+1 - n\lfloor\frac{i}{n}\rfloor\). A '1' denotes an obstacle and a '0' denotes a free path.

sample

2 2 3

111101111