Description

Problem Description

This is an interactive problem.

You are trapped in a maze, and you need to find the map of this maze.

The maze is an $n\times n$ grid. Each cell is either an obstacle or a road. Obstacles are represented by 1, and roads are represented by 0. Coordinates are numbered from top to bottom and from left to right; the cell in row $i$ and column $j$ has coordinates $(i,j)$.

Two cells are defined to be connected if and only if they share a common edge (4-connected). It is guaranteed that there exists exactly one connected component made of 0, and your starting point is inside this connected component.

Implementation Details

You need to implement a function:

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

The parameters are three integers $x,y,n$, and the return value is a string. Here, $x,y$ indicate that your coordinate is $(x,y)$ ($1<x,y<n$), and $n$ is the size of the map.

In the string you return, the $i$-th character ($0\le i<n\times n$) is 1 meaning that the cell in row $\lfloor\dfrac{i}{n}\rfloor+1$ and column $i+1-n\lfloor \dfrac{i}{n}\rfloor$ of the map is an obstacle; otherwise it is a road.

You may call the following function to find the answer:

bool move_to(char position)

Here position is any one of WASD, representing an attempt to move up, left, down, right respectively (i.e. decrease the row index by one, decrease the column index by one, increase the row index by one, increase the column index by one). If this function returns 1, it means you successfully moved one cell in that direction; otherwise, there is an obstacle in that direction and the move fails. Note that except at the very beginning, you cannot obtain your current coordinates from the interactor. If position is invalid, the interactor’s behavior is undefined.

It is guaranteed that the map is fixed from the start and will not be constructed dynamically. It is guaranteed that the first column, the first row, the $n$-th column, and the $n$-th row are all obstacles.

Your function may be called multiple times, please pay attention to initialization.

Input Format

You cannot read this part. It contains $n$ and the map. The input file is provided in encrypted form, and the interactor will not store it in decrypted form either.

Output Format

There is no output.

Hint

Example Interaction Process

Suppose the map is

1111
1011
1001
1111

The initial parameters passed in are $(2,2,4)$.

The following is one valid interaction process:

Constraints and Limits

The time limit for this problem is $2$ seconds, the memory limit is $512\text{MB}$, and it is guaranteed that in the worst case the interactive library uses less than $0.5$ seconds and less than $15\text{MB}$ of memory.

First, interactive problems are subject to the same limits as regular problems. For example, TLE / MLE will cause the whole test point to score $0$.

On this basis, you score points if and only if the maze map you report is completely correct. Let the maximum number of times you call the function in a single run be $W$. Then you get full score for that test point if and only if $W\le 5\times 10^5$.

For $100\%$ of the data, $5\le n\le 500$. Let the number of times your function is called be $x$ (equivalent to multiple test cases, and you need to re-initialize), then $1\le x\le 50$. The detailed constraints are as follows, where $(T)$ means this test point is worth $T$ points.

• Test point $1\ (8)$: $n=5,x\le 50$.
• Test point $2\ (8)$: $n=7,x\le 50$.
• Test point $3\ (20)$: $n\le 10,x\le 50$.
• Test point $4\ (10)$: $n\le 500,x\le 7$. It is guaranteed that there exists exactly one connected component made of 1.
• Test point $5\ (10)$: $n\le 20,x\le 20$.
• Test point $6\ (10)$: $n\le 50,x\le 20$.
• Test point $7\ (9)$: $n\le 100,x\le 10$.
• Test point $8\ (10)$: $n\le 200,x\le 7$.
• Test point $9\ (15)$: $n\le 500,x\le 7$.

How to Debug an Interactive Problem

The interaction process of this problem is too simple, so this problem does not provide an interactor. Please write your own.

If you do not know how to do it: just write a program that reads the map and implements the move_to function, then put your solution function inside it and run.

Translated by ChatGPT 5