[Silver] 2D Conveyor Belt Debugging

Debugging Help
#1

Problem Info

USACO 2024 December Contest, Silver
Problem 3. 2D Conveyor Belt

Link: https://usaco.org/index.php?page=viewproblem2&cpid=1448

What I’ve Tried

I have checked the editorial and it aligns with my ideas:

  1. Find out the answer considered every query has been applied
  2. Process queries in reversed order
  3. For the current query, mark all other cells that point to the current cell (I used bfs)

I pass test cases 1, 2, 3, 6, and 10.

I have also tried using ChatGPT and it has been unable to debug my solution. I would appreciate any help!

My Work

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> dx = {0, 0, 1, -1};
vector<int> dy = {1, -1, 0, 0};
vector<char> opposite_direction = {'L', 'R', 'U', 'D'};

struct Query {
    int r, c;
    char direction;
};

void printCoord(int x, int y) {
    cout << "(" << x << ", " << y << ")\n";
}

void bfs(int n, int& ans, queue<pair<int, int>>& q, vector<vector<bool>>& usable, vector<vector<char>>& grid) {
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = cur.first; int y = cur.second;
        for (int k=0; k<4; k++) {
            int r = x + dx[k]; int c = y + dy[k];
            if (r > 0 && r <= n && c > 0 && c <= n) {
                if (!usable[r][c] && (grid[r][c] == opposite_direction[k] || grid[r][c] == '?')) {
                    usable[r][c] = true;
                    q.push({r, c});
                    ans++;
                }
            }
        }
    }
}

int main() {
    int n, num_queries; cin >> n >> num_queries;
    vector<vector<char>> grid(n+1, vector<char>(n+1, '?'));
    vector<vector<bool>> usable(n+1, vector<bool>(n+1, false));
    vector<Query> queries;
    for (int i=0; i<num_queries; i++) {
        int r, c; char d; cin >> r >> c >> d;
        Query cur; cur.r = r; cur.c = c; cur.direction = d;
        queries.push_back(cur);
        grid[r][c] = d;
    }
    int ans = 0;
    queue<pair<int, int>> q;
    for (int i=1; i<=n; i++) {
        if (grid[i][1] == '?' || grid[i][1] == 'L') {usable[i][1] = true;}
        if (grid[i][n] == '?' || grid[i][n] == 'R') {usable[i][n] = true;}
    }
    for (int j=1; j<=n; j++) {
        if (grid[1][j] == '?' || grid[1][j] == 'U') {usable[1][j] = true;}
        if (grid[n][j] == '?' || grid[n][j] == 'D') {usable[n][j] = true;}
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (usable[i][j]) {
                q.push({i, j});
            }
        }
    }
    bfs(n, ans, q, usable, grid);
    ans = 0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (usable[i][j]) {
                ans++;
            }
        }
    }
    vector<int> answer;
    for (int i=num_queries-1; i>=0; i--) {
        answer.push_back(n*n - ans);
        int x = queries[i].r; int y = queries[i].c; char d = queries[i].direction;
        grid[x][y] = '?';
        if (!usable[x][y]) {
            for (int k=0; k<4; k++) {
                int r = x + dx[k]; int c = y + dy[k];
                if (r > 0 && r <= n && c > 0 && c <= n) {
                    if (usable[r][c] && (grid[r][c] == opposite_direction[k] || grid[r][c] == '?')) {
                        usable[x][y] = true;
                        ans++;
                        break;
                    }
                }
                else {
                    usable[x][y] = true;
                    ans++;
                    break;
                }
            }
        }
        if (usable[x][y]) {
            q.push({x, y});
            bfs(n, ans, q, usable, grid);
        }
    }
    for (int i=num_queries-1; i>=0; i--) {
        cout << answer[i] << '\n';
    }
}