ICPC 2024 - L. Where Am I Now?

#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;
}

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2024\\L. Where Am I Now?}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

We know the full map of open cells and walls, but not our starting cell or initial facing direction. In each round we may turn left, turn right, or step forward, and we are told the distance to the next wall in the direction we currently face. We must either determine our exact global position or prove that no strategy can do so.

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item By exploring safely, we can recover the entire connected component of open cells that contains the starting cell, in our own local coordinate system.
    \item The unknown start state only affects how this local component is embedded into the global map: translation plus one of the four rotations.
    \item Therefore, after the exploration, all remaining ambiguity is geometric. We simply enumerate all embeddings of the explored local component into the given map.
    \item 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 \texttt{no}.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Starting from the unknown initial cell, perform a DFS of the reachable open component.

    \item Use our own local coordinate system. At every visited local cell:
    \begin{itemize}[leftmargin=*]
        \item rotate through all four directions;
        \item use the returned distance to determine whether the adjacent square is open;
        \item if it is open and unvisited, step there recursively and then backtrack.
    \end{itemize}
    This reconstructs the full local graph of the connected component.

    \item Independently compute all connected components of the given global map.

    \item 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.

    \item Among all local cells, find one whose image is identical in every valid embedding. If none exists, output \texttt{no}.

    \item 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.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
The DFS reconstructs exactly the connected component of the starting cell in local coordinates.

\paragraph{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. \qed

\paragraph{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.

\paragraph{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. \qed

\paragraph{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.

\paragraph{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. \qed

\paragraph{Lemma 4.}
If no local cell has a common image across all valid embeddings, then it is impossible to determine the exact position.

\paragraph{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. \qed

\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.

\paragraph{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 \texttt{yes} is correct. Otherwise, by Lemma 4, answering \texttt{no} is correct. Hence the algorithm is correct in all cases. \qed

\section*{Complexity Analysis}

Let $m$ be the size of the reachable component and let $rc \le 10^4$ be the map size.

\begin{itemize}[leftmargin=*]
    \item The interactive DFS visits each reachable cell once and checks four directions, so it uses $O(m)$ steps and turns.
    \item Computing global connected components is $O(rc)$.
    \item 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.
\end{itemize}

The memory usage is $O(rc)$.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item The program maintains its own local orientation and updates it after every turn, so all explored edges are recorded in a consistent local frame.
    \item Backtracking after DFS recursion restores both the previous local cell and the previous facing direction.
    \item Only rotations are considered, not reflections, because the unknown initial facing direction can rotate the local frame but cannot mirror it.
\end{itemize}

\end{document}