Stones
unknown
c_cpp
a year ago
2.1 kB
6
Indexable
Never
#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; }