C++ Implementation of a Ball Movement Algorithm

#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);
#define int long long
#define vt vector
#define pb emplace_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f3f3f3f3f
#define PI pair<int, int>
#define rep(i, from, to) for (int i = from; i <= to; ++i)
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
// #pragma GCC target("avx,avx2,fma")
const int mxn = 16, MOD = 1e9 + 7;

int n, m;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
struct State {
    int ori = 0; // 0: 往下掉, 1: 往右掉, 2: 往上掉, 3: 往左掉
    vt<PI> balls; // 球的位置
};
bool operator < (State a, State b) {
    if (a.ori == b.ori) return a.balls < b.balls;
    return a.ori < b.ori;
}

vt<vt<char>> a;
map<State, int> dis;


void solve() {
    cin >> n >> m;
    vt<vt<char>> a;
    a.resize(n, vt<char> (m));
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) cin >> a[i][j];
    }

    // get current balls and clear map
    auto getBalls = [&]() { 
        vt<PI> res;
        rep(i, 0, n - 1) {
            rep(j, 0, m - 1) {
                if (a[i][j] == 'b') {
                    res.pb(i, j);
                    a[i][j] = 's';
                }
            }
        }
        return res;
    };

    // place balls on the map
    auto placeBalls = [&](vt<PI> balls) {
        for (auto [x, y] : balls) a[x][y] = 'b';
    };

    // move balls to make them stable
    auto update = [&](State u) {
        auto checkOut = [&] (int x, int y) {return x < 0 or y < 0 or x == n or y == m;};
        auto checkMove = [&](int x, int y) {
            if ((x >= 0 and y >= 0 and x < n and y < m and a[x][y] == 's') or checkOut(x, y)) return 1;
            return 0;
        };
        
        rep(_, 1, 3) { // 最多跑三次可以讓大家都到位
            rep(i, 0, n - 1) {
                rep(j, 0, m - 1) {
                    if (a[i][j] == 'b') {
                        int x = i, y = j;
                        int nx = x + dx[u.ori], ny = y + dy[u.ori];
                        while (checkMove(nx, ny)) {
                            if (checkOut(nx, ny)) {
                                a[x][y] = 's';
                                break;
                            }
                            else swap(a[x][y], a[nx][ny]);
                            x = nx; y = ny;
                            nx = x + dx[u.ori]; ny = y + dy[u.ori];
                        }
                    }
                }
            }
        }
    };
    auto checkFinish = [&](State u) {
        if (sz(u.balls) == 0) {
            cout << dis[u] << '\n';
            exit(0);
        }
    };

    State init;
    init.balls = getBalls();
    init.ori = 0;
    dis[init] = 0;
    queue<State> q;
    q.push(init);
    while (sz(q)) {
        State u = q.front(); q.pop();

        State u1 = u;
        u1.ori = (u.ori + 1) % 4;
        placeBalls(u1.balls);
        update(u1);
        u1.balls = getBalls();
        if (dis.find(u1) == dis.end()) {
            dis[u1] = dis[u] + 1;
            q.push(u1);
        }
        checkFinish(u1);

        u1 = u;
        u1.ori = (u.ori + 3) % 4;
        placeBalls(u1.balls);
        update(u1);
        u1.balls = getBalls();
        if (dis.find(u1) == dis.end()) {
            dis[u1] = dis[u] + 1;
            q.push(u1);
        }
        checkFinish(u1);
    }
    cout << "-1\n";
}

signed main(void){
    #ifdef AutoIO
    freopen("P:\\Code\\C\\input.txt","r",stdin);
    freopen("P:\\Code\\C\\output.txt","w",stdout);
    #endif
    fio
    int t = 1;
    // cin >> t;
    while (t--) solve();
}