問題描述：
在3×3的棋盤上，擺有八個棋子，每個棋子上標(biāo)有1至8的某一數(shù)字。棋盤中留有一個空格，空格用0來表示。空格周圍的棋子可以移到空格中。要求解的問題是：
給出一種初始布局（初始狀態(tài)）和目標(biāo)布局（設(shè)目標(biāo)狀態(tài)為123804765），找到一種最少步驟的移動方法，實現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變。

輸入

輸入初始狀態(tài)，一行九個數(shù)字，空格用0表示

輸出

只有一行，該行只有一個數(shù)字，表示從初始狀態(tài)到目標(biāo)狀態(tài)需要的最少移動次數(shù)(一定能到達(dá)目標(biāo)狀態(tài))

樣例輸入

283104765

樣例輸出

4

解題思路：
這題與八數(shù)碼問題I-bfs和map標(biāo)記的區(qū)別就是輸入方式換了，這樣子輸入，有種情況比如028137465(隨便舉的例子),由于第一個元素是0，所以我們用%去最后面的元素的時候，我們?nèi)〔坏?，所以我們用另外一種方式取，每次取第一個元素，將輸入的數(shù)除以100000000，就可以得到第一個元素，然后%10得到就好了。

然后，這題我們用雙向bfs寫！

代碼如下：

#include <iostream> #include <queue> #include <map> using namespace std; map<int, int>dis; map<int, int>vis; int e = 123804765; int n; int mp[4][4]; int ans;int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; int r, c;void fff1(int t) {int div = 100000000;for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++) {mp[i][j] = (t / div) % 10;if (mp[i][j] == 0) {r = i;c = j;}div = div / 10;} }int fff2() {int tmp = 0;for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++) {tmp = tmp * 10 + mp[i][j];}return tmp; }int dbfs(int s) {vis[s] = 1;//從起點開始搜標(biāo)記為1vis[e] = 2;//從終點開始搜標(biāo)記為2dis[s] = 0, dis[e] = 1;//這里終點距離為1，很容易想到是因為什么！想不到可以留言，我來幫你解答queue<int>q1, q2;q1.push(s);q2.push(e);while (q1.size() && q2.size()) {bool flag = 0;int t ;int v;if (q1.size() < q2.size()) {t = q1.front();q1.pop(); // cout << t << endl;flag = 1;} else {t = q2.front();q2.pop(); // cout << t << endl;flag = 0;}fff1(t);for (int i = 0; i < 4; i++) {int xx = r + dx[i], yy = c + dy[i];if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3) {swap(mp[xx][yy], mp[r][c]);v = fff2();if (!dis.count(v)) {dis[v] = dis[t] + 1;vis[v] = vis[t];if (flag)q1.push(v);elseq2.push(v);} else if (vis[v] + vis[t] == 3)//相遇 {ans = dis[v] + dis[t];return ans;}swap(mp[xx][yy], mp[r][c]);}}}return -1; }int main() {cin >> n;cout << dbfs(n) << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的八数码问题II-双向bfs和map标记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。