Stones

mail@pastecode.io avatar
unknown
c_cpp
a year ago
2.1 kB
6
Indexable
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MOD (int) 1e9 + 7
#define all(x) begin(x), end(x)
typedef long long ll;
using namespace std;
template <typename T> // cin >> vector<T>
istream &operator>>(istream &istream, vector<T> &v) {
    for (auto &it : v)
        cin >> it;
    return istream;
}
template <typename T> // cout << vector<T>
ostream &operator<<(ostream &ostream, const vector<T> &c) {
    for (auto &it : c)
        cout << it << " ";
    return ostream;
}

void solve(void) 
{
    vector<vector<int>> a(3, vector<int>(3, -1));

    for(int i = 0; i < 3; i++) {
        cin >> a[i];
    }

    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    queue<vector<vector<int>>> q;
    queue<int> d;
    q.push(a);
    d.push(0);
    map<vector<vector<int>>, bool> vis;
    vis[a] = true;
    while(!q.empty()) {
        vector<vector<int>> curr = q.front(); q.pop();
        int moves = d.front(); d.pop();
        bool done = true;
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                if(curr[i][j] == 0) done = false;
            }
        }

        if(done) {
            cout << moves;
            break;
        }
        
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                if(curr[i][j]) {
                    for(int k = 0; k < 4; k++) {
                        int x = i + dx[k], y = j + dy[k];
                        if(x < 0 || x >= 3 || y < 0 || y >= 3) continue;
                        curr[i][j]--;
                        curr[x][y]++;
                        if(!vis[curr]) {
                            vis[curr] = true;
                            q.push(curr);
                            d.push(moves + 1);
                        }
                        curr[i][j]++;
                        curr[x][y]--;
                    }
                }
            }
        }
    }    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}