Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <map>
- using namespace std;
- struct pawn {
- string S;
- int distance;
- vector<int> v;
- };
- bool check_if_pawns_are_ok(string &s) {
- if(s[0] == '1') {
- int idx = -1;
- for(int i = 0; i < (int) s.size(); i++) {
- if(s[i] != '1') {
- idx = i;
- break;
- }
- }
- if(idx != -1) {
- while(s[idx] == '0' and idx < (int) s.size()) {
- idx++;
- }
- for(int i = idx; i < (int) s.size(); i++) {
- if(s[i] != '2') {
- return false;
- }
- }
- }
- return true;
- }
- return false;
- }
- map<string, bool> visited;
- map<int, pair<string, int> > mapa;
- int main()
- {
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- vector<int> v(n);
- string s = "";
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- s += (v[i] + '0');
- }
- queue<pawn> Q;
- vector<int> emp;
- visited[s] = true;
- pawn tmp;
- tmp.S = s;
- tmp.distance = 0;
- tmp.v = emp;
- Q.push(tmp);
- while(!Q.empty()) {
- tmp = Q.front();
- Q.pop();
- if(check_if_pawns_are_ok(tmp.S)) {
- cout << tmp.distance << endl;
- // print the steps
- for(int i = 0; i < tmp.v.size(); i++) {
- cout << tmp.v[i] << " ";
- }
- return 0;
- }
- for(int i = 0; i < (int) tmp.S.size(); i++) {
- if(tmp.S[i] == '1') {
- if(i - 1 >= 0 and tmp.S[i - 1] == '0') {
- string ps = tmp.S;
- ps[i] = '0';
- ps[i - 1] = '1';
- if(!visited[ps]) {
- visited[ps] = true;
- pawn new_pawn;
- new_pawn.S = ps;
- new_pawn.distance = tmp.distance + 1;
- vector<int> steps = tmp.v;
- steps.push_back(i + 1);
- new_pawn.v = steps;
- Q.push(new_pawn);
- }
- }
- if(i - 2 >= 0 and tmp.S[i - 1] != '0' and tmp.S[i - 2] == '0') {
- string ps = tmp.S;
- ps[i] = '0';
- ps[i - 2] = '1';
- if(!visited[ps]) {
- visited[ps] = true;
- pawn new_pawn;
- new_pawn.S = ps;
- new_pawn.distance = tmp.distance + 1;
- vector<int> steps = tmp.v;
- steps.push_back(i + 1);
- new_pawn.v = steps;
- Q.push(new_pawn);
- }
- }
- }
- else if(tmp.S[i] == '2') {
- if(i + 1 < (int) tmp.S.size() and tmp.S[i + 1] == '0') {
- string ps = tmp.S;
- ps[i] = '0';
- ps[i + 1] = '2';
- if(!visited[ps]) {
- visited[ps] = true;
- pawn new_pawn;
- new_pawn.S = ps;
- new_pawn.distance = tmp.distance + 1;
- vector<int> steps = tmp.v;
- steps.push_back(i + 1);
- new_pawn.v = steps;
- Q.push(new_pawn);
- }
- }
- if(i + 2 < (int) tmp.S.size() and tmp.S[i + 1] != '0' and tmp.S[i + 2] == '0') {
- string ps = tmp.S;
- ps[i] = '0';
- ps[i + 2] = '2';
- if(!visited[ps]) {
- visited[ps] = true;
- pawn new_pawn;
- new_pawn.S = ps;
- new_pawn.distance = tmp.distance + 1;
- vector<int> steps = tmp.v;
- steps.push_back(i + 1);
- new_pawn.v = steps;
- Q.push(new_pawn);
- }
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement