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) {
dis[t]=dis[s]+w;
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(grid[i][j]=='C')
{
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
adj[i*n+j].pb({i*n+j-1,0}),
adj[i*n+j-1].pb({i*n+j,0}),
adj[i*n+j+250000].pb({i*n+j-1+250000,0}),
adj[i*n+j-1+250000].pb({i*n+j+250000,0});
}
}
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.
Question
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?