Find a way (DFS BFS)

//新生训练

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
using PII = pair<int, int>;

const int N = 205;
const int inf = 0x3f3f3f3f;
int n, m;
int l;

int dis1[N][N];
int dis2[N][N];

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

char a[N][N];

int yx, yy, mx, my;

void bfs1(int fx, int fy)
{
	queue<PII> q;
	q.push({fx, fy});
	dis1[fx][fy] = 0;
	while (!q.empty())
	{
		PII t = q.front();
		q.pop();
		int x = t.first, y = t.second;
		for (int i = 0; i < 4; ++i)
		{
			int ix = x + dx[i], iy = y + dy[i];
			if (ix > 0 && iy > 0 && ix <= n && iy <= m && dis1[ix][iy] == -1 && a[ix][iy] != '#')
			{
				q.push({ix, iy});
				dis1[ix][iy] = dis1[x][y] + 1;
			}
		}
	}
}

void bfs2(int fx, int fy)
{
	queue<PII> q;
	q.push({fx, fy});
	dis2[fx][fy] = 0;
	while (!q.empty())
	{
		PII t = q.front();
		q.pop();
		int x = t.first, y = t.second;
		for (int i = 0; i < 4; ++i)
		{
			int ix = x + dx[i], iy = y + dy[i];
			if (ix > 0 && iy > 0 && ix <= n && iy <= m && dis2[ix][iy] == -1 && a[ix][iy] != '#')
			{
				q.push({ix, iy});
				dis2[ix][iy] = dis2[x][y] + 1;
			}
		}
	}
}

void solve()
{
	while (cin >> n >> m)
	{
		memset(dis1, -1, sizeof dis1);
		memset(dis2, -1, sizeof dis2);
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= m; ++j)
			{
				cin >> a[i][j];
				if (a[i][j] == 'Y')
				{
					yx = i, yy = j;
				}
				else if (a[i][j] == 'M')
				{
					mx = i, my = j;
				}
			}
		}
		bfs1(yx, yy);

		bfs2(mx, my);

		int ans = inf;
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= m; ++j)
			{
				if (a[i][j] == '@' && ~dis1[i][j])
					ans = min(dis1[i][j] + dis2[i][j], ans);
			}
		}
		cout << ans * 11 << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

 //笔者学艺不精,此题还是稍显吃力 qwq ;

~~~//仅当笔者个人备忘录使用。

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/513188.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

springboot实战---6.项目发布

&#x1f388;个人主页&#xff1a;靓仔很忙i &#x1f4bb;B 站主页&#xff1a;&#x1f449;B站&#x1f448; &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;Springboot &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&…

深入C语言:探究static关键字的奥秘

文章目录 一、链接属性二、static变量1、定义静态局部变量2、在函数内部使用静态变量3、函数中静态局部变量与递归 三、static变量与全局变量的区别1、存储期与生命周期2、可见性与作用域3、使用场景4、静态与动态内存分配 注意事项 当用于不同的上下文环境时&#xff0c; sta…

nginx配置多vue项目

1. 找到linux docker安装好的nginx目录文件 进入nginx内 把打包好的vue项目放在html文件下 如上 三个文件夹下对应着三个不同的vue项目 2. 配置default.conf的配置文件&#xff0c; 一个nginx配置文件可以多个项目进行代理 进入到conf 找到conf.d下面的default.conf 文件…

Springboot自动获取接口实现

ServiceLoader加载接口实现步骤 1.编写接口 public interface CommunicationAdapterFactory {void setKernel(LocalKernel kernel);boolean providesAdapterFor(Vehicle vehicle);BasicCommunicationAdapter getAdapterFor(Vehicle vehicle); }2.编写实现 // 实现类 1 publi…

EasyBoss ERP支持TikTok Shop拆单发货功能,多店铺订单包裹拆分一个系统搞定

一些TikTok Shop本土卖家在运营过程中面临这样的困境&#xff1a;当顾客一次性订购多个商品&#xff0c;由于部分商品缺货或包裹超重&#xff0c;订单延迟发货或被物流限制发不出货&#xff0c;导致店铺被投诉。为了解决这一问题&#xff0c;卖家可以采取拆单发货的策略&#x…

支持各种不同系列nvdia显卡和amd显卡,DeepFaceLab安装与使用,附完整的软件打包下载一键安装

支持各种不同系列nvdia显卡和amd显卡&#xff0c;DeepFaceLab安装与使用&#xff0c;附完整的软件打包下载一键安装。 主要使用的技术&#xff1a; 1. 深度学习&#xff08;Deep Learning&#xff09; 深度学习是人工智能领域的一个重要分支&#xff0c;它通过模拟人脑的神经…

蓝桥杯 - 正则问题

解题思路&#xff1a; dfs import java.util.Scanner;public class Main {static int pos -1; // 充当charAt下标static String s;// 字符串型的静态变量public static void main(String[] args) {Scanner scanner new Scanner(System.in);s scanner.nextLine();System.ou…

Spring Boot--文件上传和下载

文件上传和下载 前言文件上传1、以MultipartFile 接口流文件&#xff0c;流的名称需要和前台传过来的名称对应上2、获取到文件名称截取后缀3、为了放置文件名重复使用uuid来随机生成id后缀4、判断转存路径中是否有这个文件夹如果没有就创建5、将文件存储到转存的目录中 文件下载…

免费AI视频工具PixVerse厉害了:可保持人物超强一致性(附详细教程)

PixVerse 上线了「Character」&#xff0c;可以在更换场景的情况下&#xff0c;保持人物的一致性。 下面就是用创建的人物角色&#xff0c;生成的不同场景下&#xff08;海边、城市街道、教室&#xff09;的视频&#xff0c;整体看一致性程度还是超出我的预期的。 PixVerse 人物…

华为服务器RAID配置教程 服务器硬盘故障处理帮助 浪潮RAID配置教程 磁盘阵列配置通用教程

前言&#xff08;本文档持续更新&#xff09; 本文主要记录服务器配置RAID&#xff08;磁盘阵列&#xff09;过程中存在的细节问题及官方文档无法解决的问题的解决方案 配置环境 华为 RH2288 v3服务器配置RAID组 如何快速配置 1.找到服务器品牌的阵列卡型号&#xff0c;找不到…

DBU-Net:用于乳腺超声图像中肿瘤分割的双分支U形网络

DBU-Net&#xff1a;用于乳腺超声图像中肿瘤分割的双分支U形网络 摘要引言材料和方法概述所提出的方法 DBU-Net Dual branch U-Net for tumor segmentation in breast ultrasound images 摘要 乳腺超声医学图像通常具有低成像质量沿着不清楚的目标边界。这些问题使得医生在诊断…

详解k8s集群内外的访问方式

文章目录 1、集群内访问2、集群外访问2.1、Ingress转发外网请求2.2、LoadBanlancer接入外网请求2.3、NodePort接入外网请求 3、总结和对比3.1、Ingress、NodePort和LoadBalancer总结3.2、Ingress和网关的区别 1、集群内访问 在k8s中创建的微服务&#xff0c;大部分都是在集群内…

收下这份地表最强参会指南,4月16日,玩转百度Create大会不迷路

欢迎来到英杰社区&#xff1a; https://bbs.csdn.net/topics/617804998 欢迎来到阿Q社区&#xff1a; https://bbs.csdn.net/topics/617897397 &#x1f4d5;作者简介&#xff1a;热爱跑步的恒川&#xff0c;致力于C/C、Java、Python等多编程语言&#xff0c;热爱跑步&#xff…

短视频素材怎么做?探索新鲜网站获取灵感

在短视频创作的过程中&#xff0c;寻找和制作高质量的素材是至关重要的。那么&#xff0c;短视频素材怎么做呢&#xff1f;让我们一起探索一些新鲜的网站&#xff0c;获取灵感和素材&#xff0c;让你的短视频作品更加别出心裁&#xff01; 蛙学网——中国 国内首推荐蛙学网&a…

dm控制台工具console

DM控制台工具console console工具介绍 DM控制台工具是管理和维护数据库的基本工具。 通过使用控制台工具&#xff0c;数据库管理员可以完成以下功能: ◆服务器参数配置 ◆管理DM服务 ◆脱机备份与还原 ◆查看系统信息 ◆查看许可证信息 一 登录console [dmdbatest1 tool]$ pwd…

3.java openCV4.x 入门-数据类型(CvType)与Scalar

专栏简介 &#x1f492;个人主页 &#x1f4f0;专栏目录 点击上方查看更多内容 &#x1f4d6;心灵鸡汤&#x1f4d6;我们唯一拥有的就是今天&#xff0c;唯一能把握的也是今天 &#x1f9ed;文章导航&#x1f9ed; ⬆️ 2.hello openCV ⬇️ 4.待更新 数据类型&#xff…

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!)

目录 一、前言 二、什么是字典序 &#xff1f; ✨字典序概念 ✨深度理解字典序 ✨字典序排序的重要性和应用场景 三、常考面试题 ✨ 下一个排列 ✨ 字典数排序 ✨ 字典序最小回文串 四、共勉 一、前言 经常刷算法题的朋友&#xff0c;肯定会经常看到题目中提到 字典序 这样…

AutoMQ 如何实现分区持续重平衡?

01 引言 在一个线上 Kafka 集群中&#xff0c;流量的波动、Topic 的创建和删除、Broker 的消亡和启动都随时可能发生&#xff0c;而这些变化可能导致流量在集群各个节点间分布不均&#xff0c;从而导致资源浪费、影响业务稳定。此时则需要主动将 Topic 的不同分区在各个节点间…

mysql 磁盘空间100%

MySQL大事务可能会导致过多的占用临时文件&#xff0c;导致磁盘空间撑满的问题 本例说明下binlog cache产生的临时文件 案例复现 调小binlog_cache_size&#xff0c;让DML使用临时文件 使用存储过程模拟大事务 创建表 create table t1( id int AUTO_INCREMENT, name varchar…

[蓝桥杯练习]通电

kruskal做法(加边) #include <bits/stdc.h> using namespace std; int x[10005],y[10005],z[10005];//存储i点的x与y坐标 int bcj[10005];//并查集 struct Edge{//边 int v1,v2; double w; }edge[2000005]; int cmp(Edge a, Edge b){return a.w < b.w;} int find(i…