首页 > 试题广场 >

8 数码难题 求由给定的图(如左图所示)变到右图

[问答题]

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,感觉效率低了点,但好理解
编辑于 2019-03-11 22:20:42 回复(0)