USACO 4.4 Shuttle Puzzle

BFS with pruning with key observation that W can only moves to right, and B can only moves to left to satisfy the constraints of smallest lexicographic order. Also the judge has tight memory bounds, so decide state duplication needs to use hashing (i.e. if using a set then memory will grow out of bounds for “large” test data set.).

#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <queue>
#include <functional>

using namespace std;

typedef struct State {
    int op; // index of the hole where next operation is going to happen.
    struct State *prev;
    string state;
    int empty; // index of empty hole.
    State(int op, string state, int empty, State *prev) :
    op(op), state(state), empty(empty), prev(prev) {}
} State;

queue<State*> q;
vector<State*> sp;
string target;
string start;
State *ss;
int N;
set<int> visited;
vector<int> solution;

void setup() {
    start = string(2 * N + 1, ' ');
    target = string(2 * N + 1, ' ');
    
    for (int i = 0; i < N; ++i) {
        start[i] = 'W';
        target[i] = 'B';
    }
    
    for (int i = N + 1; i < 2 * N + 1; ++i) {
        start[i] = 'B';
        target[i] = 'W';
    }
    
    ss = new State(0, start, N, nullptr);
    q.push(ss);
    sp.push_back(ss);
}

void bfs() {
    while (!q.empty()) {
        auto s = q.front(); q.pop();
        if (s->state == target) {
            cout << "target state reached." << endl;
            while (s) {
                solution.push_back(s->op);
                s = s->prev;
            }
            return;
        }
        
        int empty = s->empty;
        
        // W_ : W move right
        if (empty > 0 && s->state[empty - 1] == 'W') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'W';
            next->state[empty - 1] = ' ';
            next->op = empty - 1;
            next->prev = s;
            next->empty--;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
        
        // _B : B move left
         if (empty < 2 * N && s->state[empty + 1] == 'B') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'B';
            next->state[empty + 1] = ' ';
            next->op = empty + 1;
            next->prev = s;
            next->empty++;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
        
        // WB_ : W jump right
        if (empty > 1 && s->state[empty - 2] == 'W' &&
            s->state[empty - 1] != 'W') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'W';
            next->state[empty - 2] = ' ';
            next->op = empty - 2;
            next->prev = s;
            next->empty -= 2;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
        
        // _WB : B jump left
        if (empty < 2 * N - 1 && s->state[empty + 2] == 'B' &&
            s->state[empty + 1] == 'W') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'B';
            next->state[empty + 2] = ' ';
            next->op = empty + 2;
            next->prev = s;
            next->empty += 2;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
    }
}

int main() {
    ifstream fin("shuttle.in");
    ofstream fout("shuttle.out");
    fin >> N;
    setup();
    bfs();
    
    int cnt = 0, size = (int)solution.size() - 1;
    for (int i = size - 1; i >= 0; --i) {
        ++cnt;
        cout << solution[i] + 1;
        fout << solution[i] + 1;
        if (cnt == 20 && i) {
            cout << endl;
            fout << endl;
            cnt = 0;
        } else if (i) {
            cout << " ";
            fout << " ";
        }
    }
    
    for (auto ptr : sp) {
        if (ptr != nullptr) {
            delete ptr; ptr = nullptr;
        }
    }
    
    cout << endl;
    fout << endl;
}