当前位置: 首页 > news >正文

4635: 【搜索】【广度优先】回家

题目描述

小 H 在一个划分成了n×m 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格(当然小 H 不可以静止不动), 但不能离开封锁线,否则就被打死了。 刚开始时他有满血 6 点,每移动一格他要消耗 1 点血量。一旦小 H 的血量降到 0, 他将死去。 他可以沿路通过拾取鼠标(什么鬼。。。)来补满血量。只要他走到有鼠标的格子,他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满,所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去, 他也不能通过拾取鼠标补满 HP。 即使在家门口死去, 他也不能算完成任务回到家中。

地图上有五种格子:

0:障碍物。

1:空地, 小 H 可以自由行走。

2:小 H 出发点, 也是一片空地。

3:小 H 的家。

4:有鼠标在上面的空地。

小 H 能否安全回家?如果能, 最短需要多长时间呢?

输入

第一行两个整数 n,m, 表示地图的大小为n×m。

下面 n 行, 每行 m 个数字来描述地图。

输出

一行, 若小 H 不能回家, 输出 -1,否则输出他回家所需最短时间。

样例输入

3 3
2 1 1
1 1 0
1 1 3

样例输出

4

Code:

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,t,r;
}na[15*15];
int n,m,ans=-1,a[15][15];
int sx,sy,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool vis[15][15][10];
queue<node>que;
void bfs(){node temp={sx,sy,0,6};que.push(temp);vis[sx][sy][6]=1;while(!que.empty()){node now=que.front();que.pop();if(a[now.x][now.y]==3&&now.r){ans=now.t;return;}for(int i=0;i<4;i++){int xx=now.x+dx[i];int yy=now.y+dy[i];int tt=now.t+1;int rr=now.r-1;if(a[xx][yy]!=0&&!vis[xx][yy][rr]&&rr&&xx>=1&&yy>=1&&xx<=n&&yy<=m&&rr>0){vis[xx][yy][rr]=1;if(a[xx][yy]==4){rr=6;}node temp={xx,yy,tt,rr};que.push(temp);}}} 
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]==2){sx=i;sy=j;}}}bfs();cout<<ans;return 0;
}

http://www.lryc.cn/news/324484.html

相关文章:

  • Uibot6.0 (RPA财务机器人师资培训第1天 )RPA+AI、RPA基础语法
  • 【吊打面试官系列】Redis篇 -Redis集群的主从复制模型是怎样的?
  • 高效的二进制列化格式 MessagePack 详解
  • 鸿蒙Harmony应用开发—ArkTS-if/else:条件渲染
  • JAVA 100道题(14)
  • STM32+ESP8266水墨屏天气时钟:简易多级菜单(数组查表法)
  • 数学建模综合评价模型与决策方法
  • window下安装并使用nvm(含卸载node、卸载nvm、全局安装npm)
  • Mysql——基础命令集合
  • 记录一次流相关故障
  • linux源配置:ubuntu、centos;lspci与lsmod命令区别
  • 面试算法-88-反转链表
  • 如何在个人Windows电脑搭建Cloudreve云盘并实现无公网IP远程访问
  • 一文详解Rust中的字符串
  • Mysql中用户密码修改
  • day14-SpringBoot 原理篇
  • ChatGPT论文指南|揭秘8大ChatGPT提示词研究技巧提升写作效率【建议收藏】
  • P1563 [NOIP2016 提高组] 玩具谜题
  • 【数据库】数据库语言
  • javascript单例模式字面量定义的接口和匿名函数定义的接口;他们之间访问私有变量和私有函数之间的区别
  • 啥是大语言模型LLM
  • vue3之路由导航故障
  • Dr4g0n
  • 蓝桥杯每日一题:扫雷
  • net core API 后台系统操作日志的实现思路
  • ORACLE 知识整理
  • 业务服务:redisson
  • 面试算法-100-零钱兑换
  • 【Leetcode每日一题】 动态规划 - 使用最小花费爬楼梯(难度⭐)(41)
  • Springboot旅游管理系统设计与实现