L. Where Am I Now?
Who am I? What am I? Why am I? These are all difficult questions that have kept philosophers reliably busy over the past millennia. But when it comes to “Where am I?”, then, well, modern smartphones and GPS satellites have pretty much taken the excitement o...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
Who am I? What am I? Why am I? These are all difficult questions that have kept philosophers reliably busy over the past millennia. But when it comes to “Where am I?”, then, well, modern smartphones and GPS satellites have pretty much taken the excitement out of that question. But what if you have no GPS at hand? In one of the World Finals 2021 problems, the Instant Car- tographic Positioning Company (ICPC) demonstrated a way to determine your current location using spiral movements and observing your surroundings. Unfortunately, their method can only be used in open areas where you can move freely without any obstacles. What if you need to locate your exact position in a closed space? How can you do it? Well, now is the time to find out. You are given a map of an area consisting of unit squares, where each square is either open or occupied by a wall. At the beginning, you are placed in one of the open unit squares, but you do not know which square it is or what direction you face. Any two individual open spaces are indistinguishable, and likewise for walls. You may walk around the area, at each step observing the distance to the next wall in the direction you face. The goal is to determine your exact position on the map.
Interaction
The first line of input contains two integers r and c (1 ≤ r, c ≤ 100) specifying the size of the map. This is followed by r lines, each containing c characters. Each of these characters is either a dot (.) denoting an open square, or a number sign (#) denoting a square occupied by a wall. At least one of the squares is open. You know you start in one of the open squares on the map, facing one of the four cardinal directions, but your position and direction is not given in the input. All squares outside the map area are considered walls. Interaction then proceeds in rounds. In each round, one line becomes available, containing a single integer d (0 ≤ d ≤ 99) indicating that you see a wall in front of you at distance d. This means there are exactly d open squares between your square and the closest wall in the current direction. You should then output a line containing one of the following:
- left to turn 90 degrees to the left,
- right to turn 90 degrees to the right,
- step to move one square forward in your current direction,
- yes i j to claim that your current position is row i, column j (1 ≤ i ≤ r, 1 ≤ j ≤ c),
- no to claim that no matter what you do, it will not be possible to reliably determine your position.
If you output yes or no, interaction stops and your program should terminate. Otherwise, a new interaction round begins. In order to be accepted, your solution must never step into a wall, and can run for at most 100 000 interaction rounds (the final round where you only report yes or no counts towards this limit).
Read Sample Interaction 1 Write
3 3
##.
#..
...
1
1
0
0
0
1
yes 2 2Read Sample Interaction 2 Write 3 5 ##.## ###.# .#.## 0 0
Read Sample Interaction 3 Write
2 1
#
.
0
yes 2 1Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
By exploring safely, we can recover the entire connected component of open cells that contains the starting cell, in our own local coordinate system.
The unknown start state only affects how this local component is embedded into the global map: translation plus one of the four rotations.
Therefore, after the exploration, all remaining ambiguity is geometric. We simply enumerate all embeddings of the explored local component into the given map.
If there exists a local cell whose image is the same global cell in every valid embedding, then walking to that local cell lets us identify the current position exactly. If no such local cell exists, then no further movement can break the symmetry, so the correct answer is
no.
Algorithm
Starting from the unknown initial cell, perform a DFS of the reachable open component.
Use our own local coordinate system. At every visited local cell:
rotate through all four directions;
use the returned distance to determine whether the adjacent square is open;
if it is open and unvisited, step there recursively and then backtrack.
This reconstructs the full local graph of the connected component.
Independently compute all connected components of the given global map.
For each global component of the same size as the explored one, and for each of the four rotations, normalize both point sets by translation and compare them. Every match gives one valid embedding of the local component into the global map.
Among all local cells, find one whose image is identical in every valid embedding. If none exists, output
no.Otherwise, BFS in the explored local graph from the local origin to that local cell, execute the corresponding moves, and finally output \[ \texttt{yes } i\ j \] for the common global image of that local cell. enumerate
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
The DFS reconstructs exactly the connected component of the starting cell in local coordinates.
Proof.
Whenever the current sensor value is positive, the square directly in front of us is open, so stepping there is safe. The DFS explores every such open neighbor exactly once and backtracks afterwards. Thus every reachable open square is eventually visited, and no wall is ever entered. Therefore the explored local graph is exactly the full connected component of the true starting cell. □
Lemma 2.
Every possible actual start state corresponds to a valid embedding of the explored local component into the given global map, and every valid embedding corresponds to a possible actual start state.
Proof.
By Lemma 1 the explored local graph is the full component shape. The only unknowns are which global component it is, where the local origin maps inside that component, and how the local axes are rotated relative to the global axes. Those are exactly the choices represented by translation plus one of four rotations. Hence the set of possible actual states is exactly the set of valid embeddings. □
Lemma 3.
If a local cell has the same global image in every valid embedding, then after moving to that local cell we know our exact global position.
Proof.
All valid embeddings agree on the image of that local cell, so once we physically move there, every remaining candidate start state yields the same global location. Therefore the position is known exactly. □
Lemma 4.
If no local cell has a common image across all valid embeddings, then it is impossible to determine the exact position.
Proof.
Any future sequence of moves and observations can be simulated in every valid embedding, because the explored local component is the entire reachable component. Since no local cell is mapped to the same global position in all embeddings, there always remain at least two indistinguishable possibilities with different global positions. Thus exact localization is impossible. □
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
By Lemma 2 the algorithm enumerates exactly all possible actual start states. If it finds a local cell with a common image, Lemma 3 shows that moving there and answering
yesis correct. Otherwise, by Lemma 4, answeringnois correct. Hence the algorithm is correct in all cases. □Complexity Analysis
Let $m$ be the size of the reachable component and let $rc \le 10^4$ be the map size.
The interactive DFS visits each reachable cell once and checks four directions, so it uses $O(m)$ steps and turns.
Computing global connected components is $O(rc)$.
Comparing the explored component with all candidate components under four rotations is $O(rc \log rc)$ in the implementation because normalized point lists are sorted.
The memory usage is $O(rc)$.
Implementation Notes
The program maintains its own local orientation and updates it after every turn, so all explored edges are recorded in a consistent local frame.
Backtracking after DFS recursion restores both the previous local cell and the previous facing direction.
Only rotations are considered, not reflections, because the unknown initial facing direction can rotate the local frame but cannot mirror it.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
struct Point {
int r = 0;
int c = 0;
bool operator==(const Point& other) const {
return r == other.r && c == other.c;
}
bool operator<(const Point& other) const {
if (r != other.r) {
return r < other.r;
}
return c < other.c;
}
};
Point operator+(const Point& a, const Point& b) {
return {a.r + b.r, a.c + b.c};
}
Point rotate_point(const Point& p, const int rot) {
if (rot == 0) {
return p;
}
if (rot == 1) {
return {-p.c, p.r};
}
if (rot == 2) {
return {-p.r, -p.c};
}
return {p.c, -p.r};
}
constexpr array<Point, 4> kDirDelta = {{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}};
int rows;
int cols;
vector<string> grid;
int current_distance = 0;
int orientation = 0;
vector<Point> local_cells;
vector<array<int, 4>> graph_dirs;
map<pair<int, int>, int> id_of;
void read_distance() {
cin >> current_distance;
}
void issue(const string& cmd) {
cout << cmd << '\n';
cout.flush();
if (cmd == "no" || cmd.substr(0, 3) == "yes") {
return;
}
read_distance();
}
void turn_right() {
orientation = (orientation + 1) % 4;
issue("right");
}
void turn_left() {
orientation = (orientation + 3) % 4;
issue("left");
}
void turn_to(const int target_dir) {
int diff = (target_dir - orientation + 4) % 4;
if (diff == 3) {
turn_left();
} else {
while (diff-- > 0) {
turn_right();
}
}
}
void step_forward() {
issue("step");
}
pair<int, bool> get_or_create_id(const Point& p) {
const pair<int, int> key = {p.r, p.c};
auto it = id_of.find(key);
if (it != id_of.end()) {
return {it->second, false};
}
const int id = static_cast<int>(local_cells.size());
id_of[key] = id;
local_cells.push_back(p);
graph_dirs.push_back({-1, -1, -1, -1});
return {id, true};
}
void explore(const int id) {
const Point cell = local_cells[id];
for (int step = 0; step < 4; ++step) {
const int dir = orientation;
const Point next = cell + kDirDelta[dir];
if (current_distance > 0) {
const pair<int, bool> created = get_or_create_id(next);
const int next_id = created.first;
const bool is_new = created.second;
graph_dirs[id][dir] = next_id;
graph_dirs[next_id][(dir + 2) % 4] = id;
if (is_new) {
step_forward();
explore(next_id);
turn_right();
turn_right();
step_forward();
turn_right();
turn_right();
}
}
turn_right();
}
}
struct Transformation {
int rot = 0;
Point shift;
};
vector<Point> normalize(vector<Point> pts, Point& min_point) {
min_point = *min_element(pts.begin(), pts.end());
for (Point& p : pts) {
p.r -= min_point.r;
p.c -= min_point.c;
}
sort(pts.begin(), pts.end());
return pts;
}
void solve() {
cin >> rows >> cols;
grid.resize(rows);
for (string& row : grid) {
cin >> row;
}
read_distance();
get_or_create_id({0, 0});
explore(0);
vector<Point> component_cells = local_cells;
vector<vector<Point>> map_components;
vector<vector<int>> comp_id(rows, vector<int>(cols, -1));
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
if (grid[r][c] == '#' || comp_id[r][c] != -1) {
continue;
}
const int cid = static_cast<int>(map_components.size());
queue<Point> q;
q.push({r, c});
comp_id[r][c] = cid;
map_components.push_back({});
while (!q.empty()) {
const Point cur = q.front();
q.pop();
map_components.back().push_back(cur);
for (const Point& delta : kDirDelta) {
const int nr = cur.r + delta.r;
const int nc = cur.c + delta.c;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
continue;
}
if (grid[nr][nc] == '#' || comp_id[nr][nc] != -1) {
continue;
}
comp_id[nr][nc] = cid;
q.push({nr, nc});
}
}
}
}
vector<Transformation> transforms;
for (const vector<Point>& comp : map_components) {
if (comp.size() != component_cells.size()) {
continue;
}
Point comp_min;
const vector<Point> comp_norm = normalize(comp, comp_min);
for (int rot = 0; rot < 4; ++rot) {
vector<Point> rotated;
rotated.reserve(component_cells.size());
for (const Point& p : component_cells) {
rotated.push_back(rotate_point(p, rot));
}
Point rot_min;
const vector<Point> rot_norm = normalize(rotated, rot_min);
if (rot_norm == comp_norm) {
transforms.push_back({rot, {comp_min.r - rot_min.r,
comp_min.c - rot_min.c}});
}
}
}
if (transforms.empty()) {
issue("no");
return;
}
int target_local = -1;
Point target_global;
for (int id = 0; id < static_cast<int>(component_cells.size()); ++id) {
const Point local = component_cells[id];
const Point first_image =
rotate_point(local, transforms[0].rot) + transforms[0].shift;
bool same = true;
for (const Transformation& t : transforms) {
const Point image = rotate_point(local, t.rot) + t.shift;
if (!(image == first_image)) {
same = false;
break;
}
}
if (same) {
target_local = id;
target_global = first_image;
break;
}
}
if (target_local == -1) {
issue("no");
return;
}
vector<int> parent(local_cells.size(), -1);
vector<int> parent_dir(local_cells.size(), -1);
queue<int> q;
q.push(0);
parent[0] = 0;
while (!q.empty()) {
const int u = q.front();
q.pop();
if (u == target_local) {
break;
}
for (int dir = 0; dir < 4; ++dir) {
const int v = graph_dirs[u][dir];
if (v == -1 || parent[v] != -1) {
continue;
}
parent[v] = u;
parent_dir[v] = dir;
q.push(v);
}
}
vector<int> path_dirs;
for (int cur = target_local; cur != 0; cur = parent[cur]) {
path_dirs.push_back(parent_dir[cur]);
}
reverse(path_dirs.begin(), path_dirs.end());
for (const int dir : path_dirs) {
turn_to(dir);
step_forward();
}
ostringstream out;
out << "yes " << (target_global.r + 1) << ' ' << (target_global.c + 1);
issue(out.str());
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2024/L-where-am-i-now/solution.texC++ implementationcompetitive_programming/icpc/2024/L-where-am-i-now/solution.cppStatement textcompetitive_programming/icpc/2024/L-where-am-i-now/statement.txtStatement PDFcompetitive_programming/icpc/2024/L-where-am-i-now/statement.pdfMetadatacompetitive_programming/icpc/2024/L-where-am-i-now/meta.jsonYear packetcompetitive_programming/icpc/2024/contest_problems.pdf