Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Move{
- string board;
- int count;
- };
- string s;
- vector<int> directions[9];
- //map<string, int> visited;
- unordered_map<string, int> visited;
- queue<Move> q;
- string res = "123804765";
- int main(){
- //freopen("slidingpuzzle.in", "r", stdin);
- cin >> s;
- directions[0].push_back(1);
- directions[0].push_back(3);
- directions[1].push_back(-1);
- directions[1].push_back(1);
- directions[1].push_back(3);
- directions[2].push_back(-1);
- directions[2].push_back(3);
- directions[3].push_back(-3);
- directions[3].push_back(1);
- directions[3].push_back(3);
- directions[4].push_back(-3);
- directions[4].push_back(-1);
- directions[4].push_back(1);
- directions[4].push_back(3);
- directions[5].push_back(-3);
- directions[5].push_back(-1);
- directions[5].push_back(3);
- directions[6].push_back(-3);
- directions[6].push_back(1);
- directions[7].push_back(-3);
- directions[7].push_back(-1);
- directions[7].push_back(1);
- directions[8].push_back(-3);
- directions[8].push_back(-1);
- visited[s]++;
- q.push({s, 0});
- while(!q.empty()){
- Move cur = q.front();
- q.pop();
- if(cur.board == res){
- cout << cur.count << '\n';
- return 0;
- }
- int it = cur.board.find('0');
- //cout << it << '\n';
- for(int v: directions[it]){
- string c = cur.board;
- swap(c[it+v], c[it]);
- //cout << c << '\n';
- if(visited[c] == 0){
- visited[c]++;
- q.push({c, cur.count+1});
- }
- }
- }
- cout << "0" << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
