首页 > 其他分享 >洛谷题单指南-搜索-P1443 马的遍历

洛谷题单指南-搜索-P1443 马的遍历

时间:2024-03-04 18:34:30浏览次数:23  
标签:遍历 P1443 int 洛谷题 nx ny qx qy

原题链接:https://www.luogu.com.cn/problem/P1443

题意解读:

无论是国际象棋还是中国象棋,马的活动范围都是一样的:

只不过国际象棋棋子是在格子中,中国象棋棋子是在交点,坐标的变化方式是一样的,根据此活动范围,计算马到达每一个点的最短路径。

解题思路:

根据马的活动范围,在棋盘内进行BFS遍历,每BFS一层,路径数是上一层的路径+1,并将遍历到的位置距离起点的路径更新,直到遍历完所有能达到的格子。

马的活动范围坐标变化可以用两个数组保存:

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 405, M = 405;

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

bool flag[N][M];

int a[N][M], n, m, x, y;

queue<int> qx, qy;

void bfs()
{
    qx.push(x); qy.push(y);
    a[x][y] = 0;
    flag[x][y] = true;
    while(qx.size() && qy.size())
    {
        int cx = qx.front(); qx.pop();
        int cy = qy.front(); qy.pop();

        for(int i = 0; i < 8; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if(flag[nx][ny] || nx < 1 || nx > n || ny < 1 || ny > m) continue;
            a[nx][ny] = a[cx][cy] + 1;
            flag[nx][ny] = true;
            qx.push(nx); qy.push(ny);
        }
    }
}

int main()
{
    cin >> n >> m >> x >> y;
    memset(a, -1, sizeof(a));
    bfs();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            printf("%-5d", a[i][j]);
        }
        cout << endl;
    }

    return 0;
}

 

标签:遍历,P1443,int,洛谷题,nx,ny,qx,qy
From: https://www.cnblogs.com/jcwy/p/18052385

相关文章

  • 洛谷题单指南-搜索-P2392 kkksc03考前临时抱佛脚
    原题链接:https://www.luogu.com.cn/problem/P2392解题思路:参考https://www.cnblogs.com/jcwy/p/18003097前面已经给出了二进制法的代码,这里给出DFS的代码100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=25;ints1,s2,s3,s4;inta[N],b[N],c[......
  • 洛谷题单指南-搜索-P1219 [USACO1.5] 八皇后 Checker Challenge
    原题链接:https://www.luogu.com.cn/problem/P1219题意解读:八皇后,经典回溯问题。解题思路:逐行摆放棋子,关键在于如何快速判断行、列、正斜(左上到右下)、反斜(右上到左下)方向没有已放其他棋子1、由于逐行摆放,因此行不需要判断通过一个boolcol[N]数组即可判断列上是否已摆放其他棋......
  • 洛谷题单指南-二分查找与二分答案-P3743 kotori的设备
    原题链接:https://www.luogu.com.cn/problem/P3743题意解读:设备使用的时间越久,需要充电的总时间也越多,具备单调性,根据使用的时间,计算需要充电的时间,如果充电总时间<=使用的时间,说明有电量还能富余,使用时间还可以更多,因此只需对使用时间进行二分即可。解题思路:给定设备使用的时间......
  • 洛谷题单指南-二分查找与二分答案-P1163 银行贷款
    原题链接:https://www.luogu.com.cn/problem/P1163题意解读:利率越小,贷款期限和每个月还的钱固定的情况下,越有可能能够还完全部的贷款,具备单调性,因此给定贷款利率、贷款月数、每月还款钱数,可以计算最终贷款还剩下多少,有两种情况:>=0,说明利率可能大了,要试探更小利率;<0,说明利率小了,要......
  • 关于HashMap遍历的四种方式,以及为什么要用entry
    1.问题如何遍历HashMap,以及其中一种遍历方式中,我们为何需要先转为Map.Entry后,再遍历Map呢?而且是比较推荐的方式?2.解决参考:关于HashMap遍历,为什么要用entryHashMap中推荐使用entrySet方式遍历Map类集合KV而不是keySet方式遍历2.1为何使用Map.Entry阅读《阿里巴巴Java开发手......
  • 洛谷题单指南-二分查找与二分答案-P1182 数列分段 Section II
    原题链接:https://www.luogu.com.cn/problem/P1182题意解读:每段和的最大值越小,则分段数就越多,因此可以通过给定每段和的最大值,将分段数划分为两类:<=M,>M,对每段和的最大值进行二分即可。解题思路:二分的判定条件为,给定每段和的最大值,计算分段数,计算逻辑如下:依次遍历每一个数,求当前......
  • js 遍历替换
    constreplaceIterator=(content,pattern,replacement)=>{letindex=0;letarr=[];while(true){constres=content.match(pattern);if(res===null){if(content.length){arr.push(content);}......
  • 买卖股票的最佳时机——差值的最值的遍历寻找
    题目描述:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。(1)只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算所能获取的最大利润。返回可以从这笔交易中获取的最大利润。如果不能获取任何利润......
  • 洛谷题单指南-二分查找与二分答案-P3853 [TJOI2007] 路标设置
    原题链接:https://www.luogu.com.cn/problem/P3853题意解读:相邻路标的最大距离即空旷指数,空旷指数越小,用的路标越多,因此可以根据空旷指数将使用路标情况分成两类:路标数<=K,路标数>K,对空旷指数进行二分即可。解题思路:二分的判定条件为,给定空旷指数,计算需要的路标数只需遍历每两......
  • 洛谷题单指南-二分查找与二分答案-P2678 [NOIP2015 提高组] 跳石头
    原题链接:https://www.luogu.com.cn/problem/P2678题意解读:最短跳跃距离越大,要移走的石头就越多,因此可以根据最短跳跃距离的不同把情况分为两类:移走的石头数<=M、移走的石头数>M,对最短跳跃距离二分即可。解题思路:二分的判定条件如下:对于给定最短跳跃距离,需要计算移走的石头数,......