我正在解決 Leetcode 問題https://leetcode.com/problems/sliding-puzzle/
class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
int res = 0;
set<vector<vector<int>>> visited;
queue<pair<vector<vector<int>>, vector<int>>> q;
vector<vector<int>> correct{{1, 2, 3}, {4, 5, 0}};
vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
for (int i = 0; i < 2; i) {
for (int j = 0; j < 3; j) {
if (board[i][j] == 0) q.push({board, {i, j}});
}
}
while (!q.empty()) {
for (int i = q.size() - 1; i >= 0; --i) {
vector<vector<int>> t = q.front().first;
auto zero = q.front().second; q.pop();
if (t == correct) return res;
visited.insert(t);
for (auto dir : dirs)
{
int x = zero[0] dir[0], y = zero[1] dir[1];
if (x < 0 || x >= 2 || y < 0 || y >= 3) continue;
/* option1
vector<vector<int>> cand = t;
swap(cand[zero[0]][zero[1]], cand[x][y]);
if (visited.count(cand)) continue;
q.push({cand, {x, y}});
*/
/* option2
swap(t[zero[0]][zero[1]], t[x][y]);
if (visited.count(t)) continue;
q.push({t, {x, y}});
swap(t[zero[0]][zero[1]], t[x][y]);
*/
}
}
res;
}
return -1;
}
};
如果我保留option1 remove option2它可以作業，
但是，當我保留option2洗掉option1它不起作用！
但是這兩個代碼塊應該是一樣的。我一直試圖弄清楚幾個小時。很沮喪，沒有頭緒
uj5u.com熱心網友回復：
option1和option2的目的是生成一個新的有效棋盤狀態。在您的option1中，您遵循以下狀態：
- 將當前棋盤狀態復制到一個新的臨時棋盤實體中（例如，
cand向量） - 將空瓷磚移向
dir - 如果您之前已經訪問過新狀態，請跳過以下步驟
- 將新狀態插入佇列
它作業得很好，除了記憶體利用率。這就是為什么您可能嘗試就地移動（例如，在您的option2中）。您的選項2的步驟是這樣的：
- 將空瓷磚移向
dir - 如果您在 < 之前已經訪問過新狀態，請跳過以下步驟- 這是您犯錯誤的地方
- 將新狀態插入佇列
- 將空圖塊移回其原始位置
您在第二步中犯了錯誤，因為如果已經訪問了新生成的狀態，您不會撤消更改。請檢查以下代碼，它將解決您的問題：
// option2
swap(t[zero[0]][zero[1]], t[x][y]);
if (!visited.count(t)) q.push({t, {x, y}});
swap(t[zero[0]][zero[1]], t[x][y]);
uj5u.com熱心網友回復：
當您不會撤消交換時，Bugif (visited.count(t)) continue;
基本上就在這里。visited.count(t) is true
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417240.html
標籤：
上一篇：深度優先搜索的發現時間和完成時間
下一篇：無法理解凱撒解密步驟