洛谷P1747-好奇怪的游戏(BFS)

简介: 洛谷P1747-好奇怪的游戏(BFS)

题目背景:


《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。


题目描述:



爱与愁大神坐在公交车上无聊,于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘:***(游戏名被打上了马赛克)。这个游戏类似象棋,但是只有黑白马各一匹,在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是:马可以走“日”,也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数,你能帮他解决这个问题么?


输入格式:


第1行:两个整数x1,y1


第2行:两个整数x2,y2


输出格式:


第1行:黑马到1,1的步数

第2行:白马到1,1的步数


样例输入:


12 16

18 10


样例输出:


8

9


说明/提示:


100%数据:x1,y1,x2,y2<=20(切记,n可不是开到20就OK的,地图范围开小了会WA的!!!)


AC Code:


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=101;//这是个坑点,N开小了就会WA 
bool book[N][N];//标记数组 
int m,n,p,q,head,tail;
//题目描述中说马不仅可以走日,也可以走田,所以一共有12个方向 
int dx[]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};
int dy[]={2,2,1,-1,-2,-2,-2,-2,-1,1,2,2};
struct node {
  int x,y,step;
}que[N*N];//定义结构体模拟队列 
bool judge(int x,int y) {//不越界,并且这个点没有访问过 
  if(x>=1&&x<=N&&y>=1&&y<=N&&book[x][y]==false) {
    return true;
  }
  return false;
}
void bfs(int a,int b) {
  head=tail=1;//初始化队头队尾 
  que[head].x=a;//起点入队,这次终点是(1,1) 
  que[head].y=b;
  que[head].step=0;//步数初始化为0 
  book[a][b]=true;//标记该点已走过 
  tail++;//起点入队,队尾向后移动一格 
  while(head<tail) {
    for(int i=0;i<12;i++) {//12个方向搜索 
      int tx=que[head].x+dx[i];
      int ty=que[head].y+dy[i];
      if(judge(tx,ty)) {//合法判断 
        book[tx][ty]=true;//标记新入队的点 
        que[tail].x=tx;//新的点入队 
        que[tail].y=ty;
        que[tail].step=que[head].step+1;//步数更新+1 
        tail++;//相应的队尾向后移动一格 
        if(tx==1&&ty==1) {//走到终点 
          printf("%d\n",que[tail-1].step);
          return ;
        }
      }
    }
    head++;//队头向后移动一格,继续下一个点的搜索 
  }
  return ;
}
int main() {
  memset(book,false,sizeof(book));//第一次搜索前,标记数组清零 
  scanf("%d %d",&m,&n);
  bfs(m,n);//搜索黑马 
  memset(book,false,sizeof(book));//注意:第二次搜索前,标记数组一定要再次清零!!! 
  scanf("%d %d",&p,&q);
  bfs(p,q);//搜索白马 
  return 0;
}

相关文章
|
算法 Java
【洛谷算法题】P1000-超级玛丽游戏【入门1顺序结构】
【洛谷算法题】P1000-超级玛丽游戏【入门1顺序结构】
【动态规划刷题 5】 最小路径和&&地下城游戏
【动态规划刷题 5】 最小路径和&&地下城游戏
|
9月前
|
存储 物联网
【洛谷 P1135】奇怪的电梯 题解(广度优先搜索)
这是一个关于奇怪电梯的编程问题摘要: - 电梯在每层停,且每层有特定数字 $K_i$ 决定上/下按钮的功能。 - 目标是从 $A$ 楼到 $B$ 楼,求最少按键次数,若无法到达则输出 `-1`。 - 输入包括 $N$(楼层数)、$A$(起点)和 $B$(终点),以及每层的 $K_i$ 数字。 - 使用广度优先搜索(BFS)解决,通过队列存储访问过的楼层,避免重复并计算步数。 - 当到达目标楼层时返回步数,队列空时返回 `-1`。
87 0
|
9月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
存储 C++ 容器
五道超经典题目,带你手撕链表题(多种方法实现)下
五道超经典题目,带你手撕链表题(多种方法实现)
77 1
五道超经典题目,带你手撕链表题(多种方法实现)上
五道超经典题目,带你手撕链表题(多种方法实现)
141 0
|
算法 C++
【快乐手撕LeetCode题解系列】—— 复制带随机指针的链表
哈喽各位友友们😊,我今天又学到了很多有趣的知识,现在迫不及待的想和大家分享一下!😘我仅已此文,和大家分享【快乐手撕LeetCode题解系列】—— 复制带随机指针的链表~ 都是精华内容,可不要错过哟!!!😍😍😍
92 0
|
存储 算法
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
|
索引
力扣877. 石子游戏思路
力扣877. 石子游戏思路
154 0
力扣877. 石子游戏思路
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n ,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
183 0
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)