Sliding Game, C++ (gcc)

Sliding Game

/*
19 Sliding Game
You're given a 3x3 board of a tile puzzle, with 8 tiles numbered 1 to 8, and an empty spot. 
You can move any tile adjacent to the empty spot, to the empty spot, creating an empty spot 
where the tile originally was. The goal is to find a series of moves that will solve the board, 
i.e. get [ [1, 2, 3], [4, 5, 6], [7, 8, - ]…
*/

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
class Game19
{
public:
    vector<string> play(vector<string> &board)
    {
        vector<string> res;
        int M = board.size();
        if (M == 0)
            return res;
        int N = board[0].size();
        if (N == 0)
            return res;

string target = "12345678*";
        string start("");
        for (auto x : board)
            start += x;
        if (start == target)
            return {start};

set<string> visited;
        queue<vector<string>> q; // v[0] = current status, v[1-..] path
        q.push({start});

while (q.size())
        {
            auto v = q.front(); q.pop();
            if (v[0] == target)
                return v;
            visited.insert(v[0]); // visited

// visit next 4 neighbors
            int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            vector<string> D = {"right", "left", "down", "up"};
            string s = v[0];
            int pos = s.find('*');
            int x = pos / N, y = pos % N;
            for (int i = 0; i < 4; i++)
            {
                int x2 = x + dir[i][0];
                int y2 = y + dir[i][1];
                if (x2 < 0 || y2 < 0 || x2 >= M || y2 >= N)
                    continue;
                int pos2 = x2 * N + y2;
                string t = s;
                swap(t[pos], t[pos2]); // sliding
                if (visited.count(t))
                    continue;
                vector<string> v2 = v;
                v2[0] = t;
                v2.push_back(D[i]);
                q.push(v2);
            }
        }
        return {};
    }
};

int main() // 19. Sliding Game
{
    vector<string> board = {"*23",
                            "156",
                            "478"};
    Game19 g;
    vector<string> res = g.play(board);
    for (auto x : res)
        cout << x << endl;

return 0;
}


run \| edit \| history \| help	0

Please log in to post a comment.