Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
MAC
D three integers
Dar
Fractional Knapsack
Programa 3 (corregido)
simple use of namespace
add all
gal2
VecHotel
BubDoubLinArray