首页 > 其他分享 >马的遍历(对bfs的更深一层探讨)

马的遍历(对bfs的更深一层探讨)

时间:2023-06-11 16:56:23浏览次数:33  
标签:node 遍历 int bfs vis 更深一层 que str

题目描述

有一个 n×m 的棋盘,在某个点 (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数,分别为 n,m,x,y。

输出格式

一个 n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 −1)。

输入输出样例

输入 #1
3 3 1 1
输出 #1
0    3    2    
3    -1   1    
2    1    4    

题目很简单,但是这里要注意啊,他说的最短路径,为了避免麻烦还是直接宽搜的好
我发出来主要是我发现了个很有意思的事情,先看一下我mle和tle的代码:
#include<bits/stdc++.h>
using namespace std;
const int N=500;
int n,m,a,b,mp[N][N];     
int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={2,1,-1,-2,2,1,-1,-2};
struct node{
    int x,y,step;
};
int vis[N][N];
void bfs()
{
    queue<node>que;
    node str;
    str.x=a,str.y=b,str.step=0;
    que.push(str);
    vis[a][b]=0;
    while(!que.empty()){
        node now=que.front();
        que.pop();
        vis[now.x][now.y]=now.step;
        for(int i=0;i<8;i++){
            int x1=now.x+dx[i],y1=now.y+dy[i];
            if(x1>=1&&y1>=1&&x1<=n&&y1<=m&&vis[x1][y1]==-1){
                node next;
                next.x=x1,next.y=y1,next.step=now.step+1;
                que.push(next);
            }
        }
    }
    return ;
}
int main()
{
    cin>>n>>m>>a>>b;
    memset(vis, -1, sizeof vis);
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cout<<vis[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

接着是ac的代码:

 

#include<bits/stdc++.h>
using namespace std;
const int N=500;
int n,m,a,b,mp[N][N];     
int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={2,1,-1,-2,2,1,-1,-2};
struct node{
    int x,y,step;
};
int vis[N][N];
void bfs()
{
    queue<node>que;
    node str;
    str.x=a,str.y=b,str.step=0;
    que.push(str);
    vis[a][b]=0;
    while(!que.empty()){
        node now=que.front();
        que.pop();
        for(int i=0;i<8;i++){
            int x1=now.x+dx[i],y1=now.y+dy[i];
            if(x1>=1&&y1>=1&&x1<=n&&y1<=m&&vis[x1][y1]==-1){
                node next;
                next.x=x1,next.y=y1,next.step=now.step+1;
                vis[x1][y1]=now.step+1;
                que.push(next);
            }
        }
    }
    return ;
}
int main()
{
    cin>>n>>m>>a>>b;
    memset(vis, -1, sizeof vis);
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cout<<vis[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

 

我在这里主要想讨论在for循环里面,为什么如果不先标记vis数组就会爆t爆m

因为我在外层循环是有标记的,然后呢我想了下,确实不行,因为我们这是宽搜,搜过的不能再搜了

如果不立马标记的话,会发生另外一队来搜的时候,发现你这个点还是没标记,然后再给你标记一下,这样就导致不对了

所以会增加时间和空间,就会爆掉

 




标签:node,遍历,int,bfs,vis,更深一层,que,str
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17473174.html

相关文章

  • JS中循环遍历数组的几种常用方式总结
    第一种:for循环,也是最常见的最简单的一种,也是使用频率最高的一种,虽然性能不弱,但仍有优化空间constarr=[11,22,33,44,55,66,77,88];for(leti=0;i<arr.length;i++){console.log(arr[i]);}第二种:优化版for循环constarr=[11,22,33,44,5......
  • 二叉树先序遍历算法的步骤
    //创建二叉树类型的结构体 //创建显得树节点并赋值并将该节点的左子树指针域和右子树指针域分别赋为NULL; //创建一个函数用于遍历二叉树并打印节点的值 //主函数将并将指针分别指向新的树节点  //执行遍历打印二叉树的节点的值 ......
  • 69 遍历数组 将参数以数组形式传递
    packagecom.fqs.test;publicclasshello{publicstaticvoidmain(String[]args){//需求:设计一个方法用于数组遍历每次可以写100个数组,将数组打印出来;要求遍历的结果是在一行上的。例如:[11,22,33,44,55]int[]arr={1,2,3,4,5};getArr(a......
  • 代码随想录算法训练营第十五天|● 层序遍历 10 ● 226.翻转二叉树 ● 101.对称二叉
    102.二叉树的层序遍历力扣题目链接(opensnewwindow)给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。思路:迭代法,非递归思路,借用队列,先进先出来达到层序遍历的效果。但写的过程中,我不知道该如何让同一层的数据都保存在一个数组里。看了题解发......
  • Python在循环中修改遍历的字符串
    举例展示Python在循环中修改遍历的字符串,将不会影响循环的遍历顺序和执行轮数astr="abcaef"bstr="bcef"foriinastr:ifinotinbstr:astr=astr.replace(i,'')print(i)如上示例代码中,当i='a'时,bstr中没有'a',输出'a'......
  • xml qtreewidget 的遍历
    这些都是自己工作中遇到的,不具有普遍性 xml的递归遍历voidUserTreeWidget::travelDomElement(QDomElement&ele,QStringList&listOuterId){QDomNodenode=ele.firstChild();while(!node.isNull()){QDomElementchildElement=node.toElemen......
  • 代码随想录算法训练营第十四天|理论基础 ● 递归遍历 ● 迭代遍历 ● 统一迭代
    理论基础满二叉树概念完全二叉树概念二叉搜索树概念平衡二叉搜索树概念二叉树存储方式:链式存储和顺序存储二叉树遍历方式:前中后序遍历,层次遍历。二叉树的代码定义publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.v......
  • 图的遍历
    图的遍历标签(空格分隔):DS图深度优先遍历(DFS)思路:1.定义一个bool型数组记录已被访问过的顶点,并初始化为0,表示都还没访问过2.从其中一个未被访问过的顶点出发深度优先遍历2.1如果是连通图,则此操作只执行一回,即只从一个顶点出发2.2如果不连通,则有几个联通分量就执行......
  • 数据结构与算法分析(Java语言描述)(27)—— 深度优先遍历与连通分量
    packagecom.dataStructure.graph;//求无权图的联通分量publicclassComponents{privateGraphgraph;//存放输入的数组privateboolean[]visited;//存放节点被访问状态privateintcomponentCount;//连通分量的数量privateint[]mark;//......
  • 2023-06-06:给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历 序列。 对位
    2023-06-06:给你二叉树的根结点root,请你设计算法计算二叉树的垂序遍历序列。对位于(row,col)的每个结点而言,其左右子结点分别位于(row+1,col-1)和(row+1,col+1)树的根结点位于(0,0)。二叉树的垂序遍历从最左边的列开始直到最右边的列结束,按列索引每一列上......