leetcode 773. Sliding Puzzle 滑动谜题 耗时100%

Problem: 773. Sliding Puzzle 滑动谜题

解题过程

耗时100%，用深度优先搜索超时了，而且陷入了无限循环，不太好去重的，不知道怎么做了，看了官方的题解，大概理解了其中的意思，广度优先搜索就好多了，去重方便的，状态用数字表示即可，而且步长是相等的，只要找到题目的状态，就是最短的步长，不需要考虑其他的，广度优先搜索需要拿到下一步的状态

int key = board[0][0] * 100000 + board[0][1] * 10000 + board[0][2] * 1000 + board[1][0] * 100 + board[1][1] * 10 + board[1][2] * 1;

Code

class Solution { public: int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int mi = INT_MAX; void dfs(vector<vector<int>>& board, int x, int y, int cnt, unordered_map<int, bool>& ump) { if(cnt > mi) return; int key = board[0][0] * 100000 + board[0][1] * 10000 + board[0][2] * 1000 + board[1][0] * 100 + board[1][1] * 10 + board[1][2] * 1; if(ump[key]==true) return; if(key==123450) { mi = min(mi, cnt); return; } int tmp, xx, yy; ump[key] = true; for(int i = 0; i < 4; i++) { xx = x + dir[i][0]; yy = y + dir[i][1]; if(xx < 0 || yy < 0 || xx >= 2 || yy >= 3) continue; tmp = board[xx][yy]; board[xx][yy] = 0; board[x][y] = tmp; dfs(board, xx, yy, cnt + 1, ump); board[xx][yy] = tmp; board[x][y] = 0; } } int getKey(vector<vector<int>>& board) { int key = board[0][0] * 100000 + board[0][1] * 10000 + board[0][2] * 1000 + board[1][0] * 100 + board[1][1] * 10 + board[1][2] * 1; return key; } int slidingPuzzle(vector<vector<int>>& board) { int i, j, ii = -1, jj = -1, tmp; for(j = 0; j < 3; j++) { if(board[0][j]==0) { ii = 0; jj = j; } } for(j = 2; j >= 0; j--) { if(board[1][j]==0) { ii = 1; jj = j; } } if(getKey(board)==123450) return 0; queue<pair<int, int>> qe; qe.push({getKey(board), 0}); pair<int, int> pr; vector<vector<int>> cpboard = board; int aaa, x, y, xx, yy, kkk; unordered_map<int, bool> ump; while( !qe.empty() ) { pr = qe.front(); cpboard[0][0] = pr.first/100000; aaa = pr.first%100000; cpboard[0][1] = aaa/10000; aaa = aaa%10000; cpboard[0][2] = aaa/1000; aaa = aaa%1000; cpboard[1][0] = aaa/100; aaa = aaa%100; cpboard[1][1] = aaa/10; aaa = aaa%10; cpboard[1][2] = aaa; for(int i = 0; i < 2; i++) { for(int j = 0; j < 3; j++) { if(cpboard[i][j] == 0) { x = i; y = j; break; } } } qe.pop(); if(ump.count(pr.first)!=0) continue; ump[pr.first] = true; for(int i = 0; i < 4; i++) { xx = x + dir[i][0]; yy = y + dir[i][1]; if(xx < 0 || yy < 0 || xx >= 2 || yy >= 3) continue; aaa = cpboard[xx][yy]; cpboard[x][y] = cpboard[xx][yy]; cpboard[xx][yy] = 0; kkk = getKey(cpboard); if(kkk==123450) return pr.second + 1; qe.push({kkk, pr.second + 1}); cpboard[x][y] = 0; cpboard[xx][yy] = aaa; } } // unordered_map<int, bool> ump; // unordered_map<int, bool> umpump; // dfs(board, ii, jj, 0, ump); // if(mi == INT_MAX) return -1; return -1; } };