C++ Implementation of a Ball Movement Algorithm
unknown
c_cpp
3 months ago
3.8 kB
5
Indexable
#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(); }
Editor is loading...
Leave a Comment