首页 > 其他分享 >马的遍历

马的遍历

时间:2022-08-24 11:45:27浏览次数:52  
标签:stec 遍历 int 入队 second 节点 first

开始把马的起点入队,当前节点为马的起点,再把马走日字的几个新节点入队,拓展新节点后就能把当前节点出队。

从当前节点开始,走日字的各个节点不超过边界且未曾访问则是能入队的新节点。

新节点到起点的路径长度是当前节点到起点的路径长度加一。

#include<iostream>
#include<queue>
#include<cstring>
int stec[500][500];
//两个方向上的位移数组
int dx[]={1,-1,1,-1,2,2,-2,-2};
int dy[]={2,2,-2,-2,-1,1,-1,1};
bool bound(int x,int y,int n,int m)
{
    return x>0&&y>0&&x<=n&&y<=m; 
}
void horse(int x,int y,int n,int m)
{
    std::queue<std::pair<int,int>> Q;
    stec[x][y]=0;//起点可达且路径长度是0
    Q.push({x,y});
    while(!Q.empty())
    {
        std::pair<int,int> u=Q.front();
        Q.pop();
        for(int i=0;i<8;i++)
        {
            std::pair<int,int> v(u.first+dx[i],u.second+dy[i]);//应用位移数组来拓展节点
            if(bound(v.first,v.second,n,m)&&stec[v.first][v.second]==-1)//若这个节点是从曾在队列中的节点拓展而来且不超过边界,又不认为它可达则是新节点
            {
                Q.push(v);
                stec[v.first][v.second]=stec[u.first][u.second]+1;
            }
        }
    }
}
void output(int n,int m)
{
    for(int i=1;i<=n;i++,std::endl(std::cout))
        for(int j=1;j<=m;j++)
            printf("%-5d",stec[i][j]);
}
int main()
{
    memset(stec,0xff,sizeof stec);//假设所有点都不能到达,都是-1
    int n,m,x,y;
    std::cin>>n>>m>>x>>y;
    horse(x,y,n,m);
    output(n,m);
}

 

标签:stec,遍历,int,入队,second,节点,first
From: https://www.cnblogs.com/daigemingzi/p/16619315.html

相关文章

  • leetcode 热题100刷题-二叉树的中序遍历
    题题号:94题目:二叉树的中序遍历难度:简单链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/2022/08/23答案算法思路  本题在课程中是学过的。  ......
  • 7-1 顺序表的建立及遍历
    7-1顺序表的建立及遍历分数30作者陈晓梅单位广东外语外贸大学读入n值及n个整数,建立顺序表并遍历输出。输入格式:读入n及n个整数输出格式:输出n个整数,以空格分......
  • JQuery_遍历_for循环、JQuery_遍历2_each方法
    JQuery_遍历_for循环2.遍历1.js的遍历方式*for(初始化值;循环结束条件;步长)2.jq的遍历方式1.jq对象.each(callback)2.$.each(object,[callback])3.for..of: ......
  • 算法---二叉树的前序遍历
    知识点树递归dfs广度优先搜索(BFS)描述给你二叉树的根节点root,返回它节点值的前序遍历。数据范围:二叉树的节点数量满足0≤n≤100 0\len\le100\0≤......
  • JMeter While循环控制器应用之遍历获取文件参数
    While循环控制器应用之遍历获取文件参数by:授客QQ:1033553122测试环境JMeter-5.4.1应用实现单线程在单次迭代内遍历获取文件参数说明:上图仅给出关键配置信息注意:......
  • 二叉树遍历方法总结
    二叉树基本概念面试的时候提到的树,大部分都是二叉树.所谓二叉树是树的一种特殊结构,在二叉树中每个节点最多只能有两个子节点,在二叉树中最重要的操作莫过于遍历,即......
  • 102.binary-tree-level-order-traversal 二叉树的层序遍历
    利用queue先进先出的特性进行处理,利用queue.size()来识别元素是否在二叉树的同一层,同时要注意不能直接i<q.size()来判断,因为q.size()是不断变化的。classSolution{......
  • 107.binary-tree-level-order-traversal-ii 二叉树的层序遍历II
    参考102.binary-tree-level-order-traversal二叉树的层序遍历,翻转一下结果数组就好了。classSolution{public:vector<vector<int>>levelOrderBottom(TreeNode......
  • 二叉树的统一迭代法遍历
    中序遍历中序遍历无法直接利用栈进行遍历,需要利用指针进行遍历,对栈中的节点进行操作。对于中间节点,如果指针遍历到了,但没有进行处理,就再push()一个nullptr,作为标记,说明这......
  • 树结构遍历 (深度遍历/广度遍历)
     //深度遍历结果[1,2,21,22,23,3,31,32,33];//广度遍历结果[1,2,3,21,22,23,31,32,33];      ......