C++ 实例之九宫格广度优先遍历

C++ 实例之九宫格广度优先遍历

基本思路:

广度优先遍历,每次找到1的位置,分别向上、向下、向左、向右移动。把移动后的每个状态存储到队列中,弹出队头,判断是否为最终结果状态,如果是,输出遍历的层数(即移动步数),如果不是,把现阶段状态继续执行找到1向上向下向左向右移动操作。

#include<stdio.h> 

typedef struct MyType
{
  int number[3][3];int level;
}MyType; 

MyType queue[10000]; 

MyType GetHead(int n)
{
  return queue[n];
} 

//是否为最终结果状态
int IsFind(MyType cur)
{
  int flag=1;
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
      if(cur.number[i][j]!=3*i+j+1)
      {
        flag=0;
        break;
      }
    }
  return flag;
} 

int main()
{ 

  int cnt=0;//队列中数量
  int flag=0;//是否寻找到标记
  int ans=0;//最小步数,也是扩展的层数
  int head=0;//因为不是链表,用head来表示第一个
  for(int m=0;m<3;m++)
  {
    for(int n=0;n<3;n++)
    {
      scanf("%d",&queue[cnt].number[m][n]);
    }
  }
  queue[cnt].level=0;
  cnt++;
  while(cnt!=0)
  {
    //出站
    MyType cur=GetHead(head++);
    //判断是否为最终状态
    flag=IsFind(cur);
    if(flag==1)
    {
      printf("最小步数为:%d\n",cur.level);
      break;
    }
    else   //不为最终状态,进行扩展
    {
      for(int row=0;row<3;row++)
        for(int col=0;col<3;col++)
        {
          if(cur.number[row][col]==1)  //找到1,进行扩展
          {
            //将1向上移
            if(row!=0)
            {
              MyType temp=cur;
              temp.number[row][col]=temp.number[row-1][col];
              temp.number[row-1][col]=1;
              temp.level=cur.level+1;
              queue[cnt++]=temp;
            }
            //将1向右移动
            if(col!=2)
            {
              MyType temp=cur;
              temp.number[row][col]=temp.number[row][col+1];
              temp.number[row][col+1]=1;
              temp.level=cur.level+1;
              queue[cnt++]=temp;
            }
            //将1向下移动
            if(row!=2)
            {
              MyType temp=cur;
              temp.number[row][col]=temp.number[row+1][col];
              temp.number[row+1][col]=1;
              temp.level=cur.level+1;
              queue[cnt++]=temp;
            }
            //将1向左移动
            if(col!=0)
            {
              MyType temp=cur;
              temp.number[row][col]=temp.number[row][col-1];
              temp.number[row][col-1]=1;
              temp.level=cur.level+1;
              queue[cnt++]=temp;
            }
          }
        }
    }
  }
  return 0;
}

有个问题,就是还没弄懂,怎么判断给定初始状态无解,即不可能到达最终结果状态??

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • C++ 实现求最大公约数和最小公倍数

    C++ 实现求最大公约数和最小公倍数 最大公约数 辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a, int b) { while (a != b) { if (a>b) a = a - b; else b = b - a; } return a; } 感谢阅读,希望能帮助到大家,谢

  • C++数据结构与算法之判断一个链表是否为回文结构的方法

    本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

  • C++实现 单例模式实例详解

    设计模式之单例模式C++实现 一.经典实现(非线程安全) class Singleton { public: static Singleton* getInstance(); protected: Singleton(){} private: static Singleton *p; }; Singleton* Singleton::p = NULL; Singleton* Singleton::getInstance() { if (NULL == p) p = new Singleton()

  • 学习C++编程的必备软件

    1. 前言 这一课我们来做一些 C++ 开发前的准备工作. 2. 编程的必要工具 依你看,对编程来说,什么软件是必要的呢? 如果你认真学了上一课,那你至少可以说出一种吧. 对了,就是编译器.这个重要的程序可以把你的源代码(用高级语言如 C 语言写的指令)转换成电脑可以理解的二进制码(只包含 0 和 1 的,类似 01100110001111011101010... ). 上一课我们也提了一下,每种高级语言都有对应的编译器(当然对于 Python 这样的解释性语言,就不需要编译了),光是 C++

  • C++二维数组中的查找算法示例

    本文实例讲述了C++二维数组中的查找算法.分享给大家供大家参考,具体如下: 一.问题: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数. 二.实现代码: #include <iostream> #include <vector> using namespace std; bool Find(int target, vector<vector<int>

  • C++实现单链表按k值重新排序的方法

    本文实例讲述了C++实现单链表按k值重新排序的方法.分享给大家供大家参考,具体如下: 题目要求: 给定一链表头节点,节点值类型是整型. 现给一整数k,根据k将链表排序为小于k,等于k,大于k的一个链表. 对某部分内的节点顺序不做要求. 算法思路分析及代码(C) 思路:将链表分为小于k.等于k.大于k的三个链表,然后再合并. 链表结点定义: typedef struct Node { int data; struct Node* next; }node, *pNode; 算法代码: pNode s

  • C++中指针指向二维数组实例详解

    C++中指针指向二维数组实例详解 一维指针通常用指针表示,其指向的地址是数组第一元素所在的内存地址,如下 int ary[4][5]; int(*aryp)[5] = ary; 那么ary[4]相当于int(*aryp),以下理解如此,但参数传递需要知道实参所在 的一维个数,所以传递的时候应该传递多一个参数,子数组的引用可以理解 为(*p),那么取元素就是(*p)[i],如下 void printVal(int(*aryp)[5],int irowCount){ for (int(*p)[5]

  • C++ 实例之九宫格广度优先遍历

    C++ 实例之九宫格广度优先遍历 基本思路: 广度优先遍历,每次找到1的位置,分别向上.向下.向左.向右移动.把移动后的每个状态存储到队列中,弹出队头,判断是否为最终结果状态,如果是,输出遍历的层数(即移动步数),如果不是,把现阶段状态继续执行找到1向上向下向左向右移动操作. #include<stdio.h> typedef struct MyType { int number[3][3];int level; }MyType; MyType queue[10000]; MyType Get

  • C++实现图的邻接表存储和广度优先遍历实例分析

    本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

  • Java实现利用广度优先遍历(BFS)计算最短路径的方法

    本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga

  • PHP实现二叉树的深度优先与广度优先遍历方法

    本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法.分享给大家供大家参考.具体如下: #二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $right = null; } #@param $btree 二叉树根节点 function breadth_first_traverse($btree) { $traverse_data = array(); $queue = arr

  • C++非递归队列实现二叉树的广度优先遍历

    本文实例讲述了C++非递归队列实现二叉树的广度优先遍历.分享给大家供大家参考.具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode*> q; // 队列 q.enqueue(root); TNode* p; while(q.hasElement()) { p = q.dequeue(); // 队首元素出队列 visit(p); // 访问p结点 if(p->left) q.enqu

  • 基于Java实现的图的广度优先遍历算法

    本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

  • JavaScript树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了JavaScript树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1.深度优先遍历的递归写法 function deepTraversal(node) { var nodes = []; if (node != null) { nodes.push(node); var children = node.children; for (var i = 0; i < children.length; i++) deepTraversal(children[i]);

  • python实现树的深度优先遍历与广度优先遍历详解

    本文实例讲述了python实现树的深度优先遍历与广度优先遍历.分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个节点 广度优先 顺序:A - B - C - D - E - F - G - H - I 代码实现 def breadth_travel(self, root): """利用队列实现树的层次遍历""" if root == None: r

随机推荐