九宮格

題目19.2鏈接：8 Puzzle
需要自己定義轉(zhuǎn)移狀態(tài)，并使用BFS來確定最小路徑。標(biāo)準(zhǔn)的BFS題，只不過狀態(tài)不好定義。
代碼如下：

#include <iostream> #include <cstring> #include <map> #include <queue> using namespace std;const int N = 3; const int N2 = 9; int dx[5] = {0, 0, 1, -1}; int dy[5] = {1, -1, 0, 0}; //string dir[5] = {"r", "l", "d", "u"};//右、左、下、上 char dir[5] = {'r', 'l', 'd', 'u'};//右、左、下、上 struct Puzzle {int f[N2];//矩陣數(shù)組int space;//空格的下標(biāo)string path;//路徑bool operator < (const Puzzle &p) const {//重載<，以便于map使用其為key值for(int i=0; i<N2; i++){if(f[i]==p.f[i]) continue;return f[i] > p.f[i];}return false;} }; Puzzle P; bool isTarget(Puzzle s) {for(int i=0; i<N2-1; i++){if(s.f[i]!=i+1) return 0;}return 1; } int bfs(Puzzle P) {map<Puzzle, bool> V;queue<Puzzle> Q;Q.push(P);//先進(jìn)一個(gè)初始元素V[P] = true;//標(biāo)記已訪問Puzzle u, v;while(!Q.empty()){u = Q.front();Q.pop();if(isTarget(u)) return u.path.size();//到達(dá)目標(biāo)狀態(tài)退出int sx = u.space/N, sy = u.space%N;//求空格的坐標(biāo)//cout << 1 << endl;for(int i=0; i<4; i++)//遍歷四個(gè)方向{int tx = sx + dx[i], ty = sy + dy[i];//下一步if(tx>=N || tx<0 || ty>=N || ty<0) continue;//出矩陣v = u;//新狀態(tài)swap(v.f[u.space], v.f[tx*N+ty]);v.space = tx*N+ty;if(!V.count(v))//還沒遍歷過{V[v] = true;v.path += dir[i];Q.push(v);}}}return -1; } int main() {for(int i=0; i<N2; i++){cin >> P.f[i];if(P.f[i]==0){P.space = i;}}P.path = "";cout << bfs(P) << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的挑战程序设计(算法和数据结构)—九宫格的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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