8 数码难题
求由给定的图(如左图所示)变到右图最少需要几步。
#include<cstdio> #include<queue> #include<map> using namespace std; struct State{ int state[9]; int pos; int step; }; queue<State> que; map<vector<int>,bool> vis; int dir[4] = {1,-1,3,-3}; bool Equl(int* a,int *b){ for(int i=0;i<9;i++){ if(*(a+i) != *(b+i)){ return false; } } return true; } int copy(vector<int> &vec,int *b){ int pos; for(int i=0;i<9;i++){ vec.push_back(b[i]); if(vec[i] == 0){ pos = i; } } return pos; } void gen_st(vector<int> &vec,int ap,int bp){ int t = vec[ap]; vec[ap] = vec[bp]; vec[bp] = t; } int BFS(State begin,State end){ vector<int> temp(9); copy(temp,begin.state); que.push(begin); vis[temp] = 1; while(!que.empty()){ State cur = que.front(); que.pop(); if(Equl(cur.state,end.state)){ return cur.step; } for(int i=0;i<4;i++){ int npos = cur.pos + dir[i]; if(npos>=0 && npos<9){ vector<int> temp; int cpos = cur.pos; copy(temp,cur.state); gen_st(temp,cpos,npos); if(!vis[temp]){ State next; for(int k=0;k<9;k++){ next.state[k] = temp[k]; if(temp[k] == 0) next.pos = k; } next.step = cur.step + 1; que.push(next); vis[temp] = 1; } } } } return -1; } int main(){ State begin,end; for(int i=0;i<9;i++){ scanf("%d",&begin.state[i]); if(begin.state[i] == 0){ begin.pos = i; } } begin.step = 1; for(int i=0;i<9;i++){ scanf("%d",&end.state[i]); if(end.state[i] == 0){ end.pos = i; } } int ans = BFS(begin,end); printf("%d\n",ans); }版主试试这个,map+BFS,感觉效率低了点,但好理解