main.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

const int MAX_SQUARES = 6;
const int MAX_SIDE    = 16;

short int x[MAX_SQUARES], y[MAX_SQUARES], d[MAX_SQUARES], tx[MAX_SQUARES], ty[MAX_SQUARES], n, t, a;
short int arrows[MAX_SIDE][MAX_SIDE];
short int GO[4][2] = {
    { 0, -1 }, // U
    { 1,  0 }, // R
    { 0,  1 }, // D
    { -1, 0 }, // L
};
map<short int, char> square_names;

// forward declaration
struct step;
map<long long, step> steps;
typedef map<long long, step>::iterator steps_iterator;

struct step {
    long long prev_state;
    short int clicked;
    step() {}
    step(long long prev_, short int _clicked) : prev_state(prev_), clicked(_clicked) {}

    void print_steps() {
        if (prev_state == -1) return;
        steps_iterator it = steps.find(prev_state);
        it->second.print_steps();
        cout << " " << square_names[clicked];
    }
};


// one square fits into 10 bits:
// 2 bits for direction
// 4 bits for x and y
// 64 bits can carry 6 squares. pretty good
// and 4 bits for x,y means maximum of 16x16 grids can be solved

inline long long pack() {
    long long res = 0;
    for (int i = 0; i < n; i++) {
        long long square_packed = (d[i] << 8) | (x[i] << 4) | y[i];
        res = res | (square_packed << (i * 10));
    }
    return res;
}

inline void unpack(long long state) {
    for (int i = 0; i < n; i++) {
        y[i] = state & 15;
        state >>= 4;
        x[i] = state & 15;
        state >>= 4;
        d[i] = state & 3;
        state >>= 2;
    }
}

int main(int argc, char const *argv[])
{
    // Input format
    // N                 # number of squares
    // [N lines] D X Y   # D - direction (0,1,2,3=U,R,D,L), X Y - square coordinates, (0, 0) is upper left
    // T                 # number of targets
    // [T lines] S X Y   # S - zero-based index of square to be put into this target, X Y - target coordinates
    // A                 # number of arrows
    // [A lines] D X Y   # D - direction, X Y - square coordinates
    short int i, minx = 255, miny = 255, maxx = -1, maxy = -1;

    cin >> n;
    if (n > MAX_SQUARES) {
        cerr << n << " max " << MAX_SQUARES << " can be solved" << endl;
        return 1;
    }
    if (argc - 1 == n) {
        // Add human-readable names to squares (argv[0] == program name)
        for (i = 0; i < n; i++) square_names[i] = argv[i + 1][0];
    } else {
        // .. or just use numbers to denote them
        for (i = 0; i < n; i++) square_names[i] = (char)(i + '0');
    }
    for (i = 0; i < n; i++) {
        cin >> d[i] >> x[i] >> y[i];
        tx[i] = -1;
        minx = min(x[i], minx);
        miny = min(y[i], miny);
        maxx = max(x[i], maxx);
        maxy = max(y[i], maxy);
    }
    cin >> t;
    for (i = 0; i < t; i++) {
        int s;
        cin >> s;
        cin >> tx[s] >> ty[s];
        minx = min(tx[s], minx);
        miny = min(ty[s], miny);
        maxx = max(tx[s], maxx);
        maxy = max(ty[s], maxy);
    }
    if (maxx - minx + 1 > MAX_SIDE || maxy - miny + 1 > MAX_SIDE) {
        cerr << "grid size exceeds " << MAX_SIDE << endl;
        return 1;
    }

    // place objects at the center of grid
    short int offset_x = (MAX_SIDE - (maxx - minx)) / 2;
    short int offset_y = (MAX_SIDE - (maxy - miny)) / 2;

    for (i = 0; i < n; i++) {
        x[i] += offset_x;
        y[i] += offset_y;
    }
    for (i = 0; i < n; i++) {
        if (tx[i] == -1) continue;
        tx[i] += offset_x;
        ty[i] += offset_y;
    }

    for (i = 0; i < MAX_SIDE; i++) for (int j = 0; j < MAX_SIDE; j++) arrows[i][j] = -1;
    cin >> a;
    for (i = 0; i < a; i++) {
        int d, x, y;
        cin >> d >> x >> y;
        arrows[offset_x + x][offset_y + y] = d;
    }

    cout << "============== lets go... ============" << endl;

    // Le BFS
    queue<long long> q;
    long long state = pack();
    q.push(state);
    steps[state] = step(-1, 0);
    while (!q.empty()) {
        state = q.front();
        q.pop();
        unpack(state);

        // has we solved yet?
        bool solved = true;
        for (i = 0; i < n; i++) {
            if (tx[i] == -1) continue;
            if (tx[i] != x[i] || ty[i] != y[i]) {
                solved = false;
                break;
            }
        }
        if (solved) {
            cout << "solved, winning state: " << state << endl;
            steps[state].print_steps();
            cout << endl;
            break;
        }

        // do moves and spawn new states
        for (i = 0; i < n; i++) {
            bool moved_ok = true, moving = true;
            short int cur_square = i, dir = d[i];
            while (moving) {
                x[cur_square] += GO[dir][0];
                y[cur_square] += GO[dir][1];
                if (x[cur_square] < 0 || y[cur_square] < 0 || x[cur_square] >= MAX_SIDE || y[cur_square] >= MAX_SIDE) {
                    moved_ok = false;
                    break;
                }
                if (arrows[x[cur_square]][y[cur_square]] != -1) {
                    d[cur_square] = arrows[x[cur_square]][y[cur_square]];
                }
                moving = false;
                for (short int j = 0; j < n; j++) {
                    if (i != j && j != cur_square && x[j] == x[cur_square] && y[j] == y[cur_square]) {
                        cur_square = j;
                        moving = true;
                        break;
                    }
                }
            }

            if (moved_ok) {
                long long next_state = pack();
                steps_iterator it = steps.find(next_state);

                if (it == steps.end()) {
                    steps[next_state] = step(state, i);
                    q.push(next_state);
                }
            }

            // unpack again to restore state
            unpack(state);
        }
        // end spawning states
    }
    return 0;
}