Wa in 1 Tc in Usaco Silver 2013 US Open Gravity

Problem Info

Problem Name: USACO 2013 US Open, Silver Problem 1. What’s Up With Gravity
Problem Link: What’s Up with Gravity

My Work

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxn = 510, LINF = 1e18;
int n, m, src, dest, ans;
string grid[maxn];
vector<pair<int,int>> adj[maxn*maxn*3];
vector<int> dis(maxn*maxn*3, LINF), pos(maxn*maxn*3, -1);
// pos[i] = position a cell i will be after gravity takes effect
// cell i where i < 250000 is cell with gravity moving downward
// cell i where i >= 250000 is cell with gravity moving upward
void bfs01(int src)
    deque<int> q; q.push_front(src), dis[src]=0;
    while(!q.empty()) {
        int s = q.front(); q.pop_front();
        if(s==-1) continue;
        for(auto u : adj[s]) {
            int t = u.first, w = u.second;
            if(t!=dest and t!=dest+250000) t = pos[t]; // only correct cell t to pos[t] if not cell containing 'D'
            if(t==-1) continue; // if current cell after gravity takes place is outside bounds ignore(rule 1)
            if(dis[t]==LINF) {
                if(w==0) q.push_front(t);
                else q.push_back(t);

int32_t main()
	ios_base::sync_with_stdio(false); cin.tie(0);
	ifstream cin("6.in");
	ofstream cout("gravity.out");
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> grid[i];
    for(int i = 0; i < m; i++) {
        set<int> col; col.clear();
        int J = -1;
        for(int j = 0; j < n; j++) {
            if(grid[j][i]=='#') col.insert(j);
            else if(grid[j][i]=='D') col.insert(j), J = j;
        for(int j = 0; j < n; j++) {
            if(grid[j][i]=='#') continue;
            auto x = col.lower_bound(j);
            if(x==col.end()) continue;
            int y = *x; if(J!=y) y--;
            pos[j*n+i]=y*n+i; // new cell number after gravity correction for downward gravity
        for(int j = 0; j < n; j++)
            if(grid[j][i]=='#') continue;
            auto x = col.lower_bound(j);
            if(x==col.begin()) continue; x--;
            int y = *x; if(J!=y) y++; // if j==y, we are in cell 'D' which it isnt a wall so we dont go to the next row
            pos[j*n+i+250000]=y*n+i+250000; // new cell number after gravity correction for upward gravity
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j]=='D') dest = i*n+j; //set dest
                if(pos[i*n+j]==-1){cout<<-1;return 0;}
                src = pos[i*n+j]; // set source
            if(grid[i][j]=='#') continue;
            adj[i*n+j].pb({i*n+j+250000,1}), // switch between gravities on the spot
            adj[i*n+j+250000].pb({i*n+j,1}); // same above
            if(j<m-1 and grid[i][j+1]!='#') // can move to right
                adj[i*n+j].pb({i*n+j+1,0}), // from down gravity
                adj[i*n+j+1].pb({i*n+j,0}), // same as above
                adj[i*n+j+250000].pb({i*n+j+1+250000,0}), // from up gravity
                adj[i*n+j+1+250000].pb({i*n+j+250000,0}); // same as above
            if(j and grid[i][j-1]!='#') // can move to left
    bfs01(src), ans = min(dis[dest], dis[dest+250000]);
    cout << (ans==LINF?-1:ans);

The grid is numbered in the usual way starting from 0. For cell number i, downward gravity at i = node i, upward gravity at i = node i +250000. Any edge that joins node numbers of opposite gravity has weight of 1, while edges joining node numbers in the same gravity have weight of 0. Let Pos[i] stand for node number after gravity takes place at that node ‘i’(for nodes with downward gravity, apply downward gravity, same for opposite case). We start with cell pos[C](C is cell number at cell with ‘C’, same for D) and apply 0-1 bfs to get shortest path to either node D or D+250000. If any is not valid, set it to a large number. pick the shorter of the two choices. and output result if its possible to reach either of the two else -1

What I’ve Tried

I tried downloading the test data. Testcase #6 was too large to debug. I found out my answer gives a smaller answer compared to the testdata answer.(Probably adding illegal 0 weight edges). I’ve checked the editorial but it seems to be different from my solution and more difficult to understand. Ive tried debugging for many hours but to no avail.


I’m only failing Testcase 6 for some reason. I feel like i’m missing something in the rules. Can you help me in finding the error?

What about this?

I’m not sure how I would approach generating random grids in this case.