# 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<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;
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
if(j<m-1 and grid[i][j+1]!='#') // can move to right
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.

## 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?