leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0773.cpp (1681B)

0 class Solution { 1 using type_t = pair<uint32_t, uint32_t>; 2 3 static type_t encode(const vector<vector<int>> &board) { 4 uint32_t n2p = 0; // number to position 5 uint32_t p2n = 0; // position to number 6 7 for (int i = 0; i < 2; i++) { 8 for (int j = 0; j < 3; j++) { 9 const int idx = i * 3 + j; 10 n2p |= idx << (board[i][j] * 3); 11 p2n |= board[i][j] << (idx * 3); 12 } 13 } 14 15 return {n2p, p2n}; 16 } 17 18 public: 19 int slidingPuzzle(const vector<vector<int>> &board) const { 20 static const vector<vector<int>> adj = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}; 21 22 unordered_set<uint32_t> seen; 23 queue<type_t> q; 24 25 q.push(encode(board)); 26 for (int lvl = 0; !q.empty(); lvl++) { 27 for (int k = size(q); k > 0; k--) { 28 const auto [n2p, p2n] = q.front(); 29 q.pop(); 30 31 if (n2p == 0x23445) return lvl; 32 33 const auto p = n2p & 0x7; // position of zero 34 for (const auto sp : adj[p]) { // position to swap 35 const auto sn = (p2n >> (sp * 3)) & 0x7; // number to swap 36 37 const auto sn2p = (n2p & ~((0x7 << (sn * 3)) | (0x7 << (0 * 0)))) | (p << (sn * 3)) | sp; 38 const auto sp2n = (p2n & ~((0x7 << (sp * 3)) | (0x7 << (p * 3)))) | (sn << (p * 3)); 39 40 if (!seen.count(sn2p)) { 41 q.emplace(sn2p, sp2n); 42 seen.insert(sn2p); 43 } 44 } 45 } 46 } 47 48 return -1; 49 } 50 };