We are given an n x m grid representing a parking lot. Each cell contains either a car or an empty space. Car are represented by a direction they are facing: 'N' (North), 'E' (East), 'S' (South), or 'W' (West). Empty spaces are denoted by '.'. A car can be moved if and only if the path direct in front of it is clear, meaning there are no other cars or all cars blocking its path have already been moved. The task is to find a sequence to move all cars off the grid, moving one car at a time. For each move, output the coordinates of the car being moved. The top-left corner of the grid is at (0, 0). It is guaranteed that a valid sequence exists.

Solution

The problem can be modeled as a directed graph where each car is a node. An edge from car A to car B indicates that car A must be moved before car B. This dependency graph can then be solved using a topological sort to find a valid order of removal.

The primary challenge lies in efficiently constructing this graph. A naive approach would connect a car to every other car in its line of sight, resulting in a time complexity of O(n^3), which is infeasible for larger grids.

The key optimization is to reduce the number of edges. For any given car, we only need to consider cars directly in its path:

• Same Direction: If a car is behind another car of the same direction, it only needs an edge from the car immediately in front of it. If that front car can be moved, all cars behind it in the same line can also be moved.
• Different Direction: If a car is in the path of a car facing a different direction, an edge is needed from that blocking car to the current car.

With this optimization, each car will have at most two incoming edges, leading to a much more efficient graph construction with a time complexity of O(n^2).

Code

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

struct Car {
    int id;
    int row;
    int col;
    char direction;
};

class Graph {
public:
    Graph(int numNodes) : adj(numNodes), inDegree(numNodes, 0) {}

    void addEdge(int from, int to) {
        adj[from].push_back(to);
        inDegree[to]++;
    }

    vector<int> topologicalSort() {
        vector<int> order;
        queue<int> q;

        for (int i = 0; i < inDegree.size(); ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int current = q.front();
            q.pop();
            order.push_back(current);

            for (int neighbor : adj[current]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return order;
    }

private:
    vector<vector<int>> adj;
    vector<int> inDegree;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    vector<Car> cars;
    int carId = 0;

    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] != '.') {
                cars.push_back({carId, i, j, grid[i][j]});
                carId++;
            }
        }
    }

    Graph g(cars.size());

    // Map to quickly find cars by their (row, col) position
    vector<vector<int>> carAtPosition(n, vector<int>(m, -1));
    for (int i = 0; i < cars.size(); ++i) {
        carAtPosition[cars[i].row][cars[i].col] = i;
    }

    // Build the graph
    for (const Car& car : cars) {
        int r = car.row;
        int c = car.col;
        char dir = car.direction;

        if (dir == 'N') {
            bool firstSameDir = false;
            for (int i = r - 1; i >= 0; --i) {
                if (carAtPosition[i][c] != -1) {
                    int blockingCarId = carAtPosition[i][c];
                    if (cars[blockingCarId].direction == 'N') {
                        if (!firstSameDir) {
                            g.addEdge(blockingCarId, car.id);
                            firstSameDir = true;
                        }
                    } else {
                        g.addEdge(blockingCarId, car.id);
                    }
                }
            }
        } else if (dir == 'S') {
            bool firstSameDir = false;
            for (int i = r + 1; i < n; ++i) {
                if (carAtPosition[i][c] != -1) {
                    int blockingCarId = carAtPosition[i][c];
                    if (cars[blockingCarId].direction == 'S') {
                        if (!firstSameDir) {
                            g.addEdge(blockingCarId, car.id);
                            firstSameDir = true;
                        }
                    } else {
                        g.addEdge(blockingCarId, car.id);
                    }
                }
            }
        } else if (dir == 'E') {
            bool firstSameDir = false;
            for (int j = c + 1; j < m; ++j) {
                if (carAtPosition[r][j] != -1) {
                    int blockingCarId = carAtPosition[r][j];
                    if (cars[blockingCarId].direction == 'E') {
                        if (!firstSameDir) {
                            g.addEdge(blockingCarId, car.id);
                            firstSameDir = true;
                        }
                    } else {
                        g.addEdge(blockingCarId, car.id);
                    }
                }
            }
        } else if (dir == 'W') {
            bool firstSameDir = false;
            for (int j = c - 1; j >= 0; --j) {
                if (carAtPosition[r][j] != -1) {
                    int blockingCarId = carAtPosition[r][j];
                    if (cars[blockingCarId].direction == 'W') {
                        if (!firstSameDir) {
                            g.addEdge(blockingCarId, car.id);
                            firstSameDir = true;
                        }
                    } else {
                        g.addEdge(blockingCarId, car.id);
                    }
                }
            }
        }
    }

    vector<int> removalOrder = g.topologicalSort();

    for (int id : removalOrder) {
        cout << "(" << cars[id].row << "," << cars[id].col << ")" << endl;
    }

    return 0;
}