八数码问题,就是在一个含有1-8和x的3*3方格中,每次可以将x与其相邻位置的数字交换。使得最后变成 1 2 3 4 5 6 7 8 x 你要做的就是实现八数码的解决方案,并要求交换次数最少。-笔试面试资料

这是qklbishe.com第6439 篇笔试面试资料
提供答案分析,通过本文《八数码问题,就是在一个含有1-8和x的3*3方格中,每次可以将x与其相邻位置的数字交换。使得最后变成 1 2 3
4 5 6
7 8 x 你要做的就是实现八数码的解决方案,并要求交换次数最少。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

八数码问题,就是在一个含有1-8和x的3*3方格中,每次可以将x与其相邻位置的数字交换。使得最后变成

1 2 3
4 5 6
7 8 x

你要做的就是实现八数码的解决方案,并要求交换次数最少。

八数码问题,就是在一个含有1-8和x的3*3方格中,每次可以将x与其相邻位置的数字交换。使得最后变成    1 2 3   4 5 6   7 8 x    你要做的就是实现八数码的解决方案,并要求交换次数最少。 DOA
#include<cstdio> #include<cstring> #include<map> #include<queue> #define maxn 3 using namespace std;  int aim = 0; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1};  struct Node {     int x, y;     int step = 0;     // int status;     char status[maxn][maxn]; }; Node s;  bool judge(const Node &a) {     if (a.x<0 || a.x>2 || a.y<0 || a.y>2)         return false;     return true; }  int matrix2int(char status[maxn][maxn]) {    //得到每一种状态的标识     int ans = 0;     for (int i = 0; i < 3; i++)         for (int j = 0; j < 3; j++)             ans = ans*10+status[i][j]-'0';     return ans; }  void copyM(char a[maxn][maxn], char b[maxn][maxn]) {     for(int i=0; i<3; i++)         for(int j=0; j<3; j++)             b[i][j] = a[i][j]; }  int bfs() {     queue<Node> q;     map<int, int> hashMp;     // Node next;     q.push(s);     int key = matrix2int(s.status);     if (key==aim)         return 1;     ++hashMp[key];     while (!q.empty())     {         s = q.front();         q.pop();         for (int i = 0; i < 4; i++)         {             Node next = s;             next.x = s.x+dx[i];             next.y = s.y+dy[i];             next.step = s.step+1;             if (judge(next))             {                 // copyM(s.status, next.status);                 swap(next.status[next.x][next.y], next.status[s.x][s.y]);                 int key = matrix2int(next.status);                 if (key == aim)                     return next.step;                 if (hashMp[key]==0)                 {                     q.push(next);                     hashMp[key]++;                 }             }         }     }     return -1; }  int main() {     for (int i = 0; i < 3; i++)     {         for (int j = 0; j < 3; j++)         {             scanf("%c", &s.status[i][j]);             getchar();  //吃空格和回车             if (s.status[i][j]=='x')    //把x换成0字符             {                 s.x = i, s.y = j;                 s.status[i][j]='0';             }                         }     }     aim=123456780;      printf("%dn", bfs());     return 0; }

今天 16:37:57 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 八数码问题,就是在一个含有1-8和x的3*3方格中,每次可以将x与其相邻位置的数字交换。使得最后变成 1 2 3 4 5 6 7 8 x 你要做的就是实现八数码的解决方案,并要求交换次数最少。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情