What's Up With Gravity

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <numeric>
#include <iomanip>
using namespace std;
#define pii pair<int, int>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const int dl[2] = {1, -1};
const int MOD = 1e9;
const int MAX = 505;


int n, m;
int world[MAX][MAX]; // 1 = Blocked, 0 = Empty, 2 = Start, 3 = End;
int dist[MAX][MAX][2];
pii spos, epos;
pii fall[MAX][MAX][2];

void print_world(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << world[i][j];
        }
        cout << "\n";
    }
}

void print_dist(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << dist[i][j][0] << " ";
        }
        cout << "\n";
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << dist[i][j][1] << " ";
        }
        cout << "\n";
    }
}

void input(){
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.size(); j++){
            int tmp;
            if(s[j] == '#'){
                tmp = 1;
            }
            else if(s[j] == 'C'){
                tmp = 2;
                spos = make_pair(i, j);
            }
            else if(s[j] == 'D'){
                tmp = 3;
                epos = make_pair(i, j);
            }
            else{
                tmp = 0;
            }
            world[i][j] = tmp;
        }
    }
}

// gravity: 0 = inc, 1 = dec
// (-1, -1) = dead;

void init_gravity(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            fall[i][j][0] = make_pair(-2, -2);
            fall[i][j][1] = make_pair(-2, -2);
        }
    }
}

pii check_gravity(int x, int y, int gravity){
    if(fall[x][y][gravity] != make_pair(-2, -2)){
        return fall[x][y][gravity];
    }
    if(gravity == 0){
        if(x == n - 1){
            return fall[x][y][gravity] = make_pair(-1, -1);
        }
        else if(world[x + 1][y] != 1){
            return fall[x][y][gravity] = check_gravity(x + 1, y, gravity);
        }
        else{
            return fall[x][y][gravity] = make_pair(x, y);
        }
    }
    else if(gravity == 1){
        if(x == 0){
            return fall[x][y][gravity] = make_pair(-1, -1);
        }
        else if(world[x - 1][y] != 1){
            return fall[x][y][gravity] = check_gravity(x - 1, y, gravity);
        }
        else{
            return fall[x][y][gravity] = make_pair(x, y);
        }
    }
}

void init_fall(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(world[i][j] != 1){
                check_gravity(i, j, 0);
                check_gravity(i, j, 1);
            }
        }
    }
}

void print_fall(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << "Gravity of: " << i << " " << j << "\n";
            cout << "Down: " << fall[i][j][0].first << " " << fall[i][j][0].second << "\n";
            cout << "Up: " << fall[i][j][1].first << " " << fall[i][j][1].second << "\n";
        }
    }
}

void init_dist(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            dist[i][j][0] = -1;
            dist[i][j][1] = -1;
        }
    }
}

void BFS(){
    deque<pair<pii, pii>> q; // coords, gravity
    q.push_front(make_pair(spos, make_pair(0, 0)));
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int g = q.front().second.first;
        int flips = q.front().second.second;
        q.pop_front();
        // cout << "BFS: " << x << " " << y << " " << g << " " << flips << "\n";
        if(dist[x][y][g] != -1){
            // cout << "Visited\n";
            continue;
        }
        dist[x][y][g] = flips;
        pii coords = fall[x][y][g];
        if(coords == make_pair(-1, -1)){
            for(int i = x; i < n and i >= 0; i -= g * 2 - 1){
                if(dist[i][y][g] == -1){
                    dist[i][y][g] = flips;
                }
                else{
                    dist[i][y][g] = min(dist[i][y][g], flips);
                }
            }
            // cout << "Fell out\n";
            continue;
        }
        if(coords == make_pair(x, y)){
            // cout << "No change from gravity\n";
        }
        else{
            if(x < coords.first){
                for(int i = x; i <= coords.first; i++){
                    if(dist[i][y][g] == -1){
                        dist[i][y][g] = flips;
                    }
                    else{
                        dist[i][y][g] = min(dist[i][y][g], flips);
                    }
                }
            }
            else{
                for(int i = coords.first; i <= x; i++){
                    if(dist[i][y][g] == -1){
                        dist[i][y][g] = flips;
                    }
                    else{
                        dist[i][y][g] = min(dist[i][y][g], flips);
                    }
                }
            }
            x = coords.first;
            y = coords.second;
        }
        for(int i = 0; i < 2; i++){
            int ny = y + dl[i];
            // cout << x << " " << ny << ": ";
            if(ny < 0 or ny >= m){
                // cout << "out of bounds\n";
                continue;
            }
            else if(world[x][ny] == 1){
                // cout << "blocked\n";
                continue;
            }
            else{
                // cout << "pushed\n";
                q.push_front(make_pair(make_pair(x, ny), make_pair(g, flips)));
            }
        }
        // cout << "gravity flipped\n";
        q.push_back(make_pair(make_pair(x, y), make_pair(1 - g, flips + 1)));
    }
}

void ans(){
    int ex = epos.first;
    int ey = epos.second;
    if(dist[ex][ey][0] == -1 and dist[ex][ey][1] == -1){
        cout << "-1";
    }
    else if(dist[ex][ey][0] == -1){
        cout << dist[ex][ey][1];
    }
    else if(dist[ex][ey][1] == -1){
        cout << dist[ex][ey][0];
    }
    else{
        cout << min(dist[ex][ey][1], dist[ex][ey][0]);
    }
}

int main() {
    FAST;
    freopen("gravity.in", "r", stdin);
    freopen("gravity.out", "w", stdout);
    cin >> n >> m;
    input();
    init_gravity();
    init_fall();
    // print_fall();
    // print_world();
    init_dist();
    BFS();
    // print_dist();
    ans();
}