P3855 [TJOI2008] Binary Land(BFS)(内附封面)

[TJOI2008] Binary Land

题目背景

Binary Land是一款任天堂红白机上的经典游戏,讲述的是两只相爱的企鹅Gurin和Malon的故事。两只企鹅在一个封闭的迷宫中,你可以控制他们向上下左右四个方向移动。但是他们的移动有一个奇怪的规则,即如果你按“上”或“下”方向键,两只企鹅会同时向上移动或向下移动1格;如果你按“左”方向键,则Malon向左移动1格,同时Gurin向右移动1格;如果你按“右”方向键,则Malon向右移动1格,Gurin向左移动1格。当然,如果某只企鹅被障碍挡住,它就不会移动了。另外,在迷宫的某些格子处有蜘蛛网,如果任何一只企鹅进入这种格子,则游戏失败。两只企鹅不会相互阻挡,即在相向运动时他们可以“穿过”彼此,也可以同时处于同一格子里。迷宫的某个格子上有一颗红心,游戏的任务就是使两只企鹅同时到达这个格子。

题目描述

请编写程序找出完成任务所需的最少的操作步数。如果无法完成目标,输出“no”。

输入格式

第一行包含两个整数R, C 表示迷宫的长和宽。

按下来有R行,每行包含C个字符,描述了一个迷宫。其中’#’表示企鹅不能通过的障碍物,’X’表示蜘蛛网,’.’表示空地,’G’表示Gurin的初始位置,’M’表示Malon的初始位置,’T’表示终点位置。

输入数据保证标有’G’,’M’,’T’的格子分别只有一个,保证企鹅不可能走到迷宫以外。

输出格式

输出只有一行,为最少的操作步数。如果不能完成任务,输出“no”。

样例 #1

样例输入 #1

4 7
#######
#..T..#
#G##M##
#######

样例输出 #1

4

提示

满足要求的一个操作序列为:上-右-左-左

3 ≤ R, C ≤ 30

大致思路

!BFS!

根据题目,我们需要兼顾两个点,G与M,其实这与只看一个点时相差无几,用结构体存储即可,对于特殊的移动法则,我们也可以用一个数组存储方位来实现。BFS的判重可以直接用一个四维数组,反正数据范围不大

char sm[66][66];
int n,m;
int agx[]={0,-1,0,1};
int agy[]={-1,0,1,0};
int amx[]={0,-1,0,1};
int amy[]={1,0,-1,0};
struct awsl{
	int gx,gy,mx,my,cnt;
};
bool vis[31][31][31][31];
int goalx,goaly;
queue<awsl> q;
bool flag=1;

BFS部分直接套模板就好啦,对于G与M都处于’ # '的点,我们无需让他入队,不移动肯定不会是答案,也不会是最优。若搜索结束还没有搜到,则输出“ no ”
(代码较为繁琐,其实原理是很简单的QAQ)

while(!q.empty()){
		awsl tmp,kk;
		tmp=q.front();
		q.pop();
		if(vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]==1)continue;
		vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]=1;
		if(tmp.gx==tmp.mx&&tmp.gx==goalx&&tmp.gy==tmp.my&&tmp.my==goaly){
			cout<<tmp.cnt;
			flag=0;
			break;
		}
		for(int i=0;i<4;i++){
			int new_gx,new_gy,new_mx,new_my;
			new_gx=tmp.gx+agx[i];new_mx=tmp.mx+amx[i];
			new_gy=tmp.gy+agy[i];new_my=tmp.my+amy[i];
			if(sm[new_gx][new_gy]=='X'||sm[new_mx][new_my]=='X'){
				continue;
			}
			if(sm[new_gx][new_gy]=='#'&&sm[new_mx][new_my]!='#'){
				kk.cnt=tmp.cnt+1,kk.gx=tmp.gx,kk.gy=tmp.gy;
				kk.mx=new_mx,kk.my=new_my;
				q.push(kk);
			}
			else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]=='#'){
				kk.cnt=tmp.cnt+1,kk.mx=tmp.mx,kk.my=tmp.my;
				kk.gx=new_gx,kk.gy=new_gy;
				q.push(kk);
			}
			else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]!='#'){
				kk.cnt=tmp.cnt+1,kk.mx=new_mx,kk.my=new_my;
				kk.gx=new_gx,kk.gy=new_gy;
				q.push(kk);
			}
		}
	}
	if(flag)cout<<"no";

AC CODE

#include<bits/stdc++.h>
using namespace std;
char sm[66][66];
int n,m;
int agx[]={0,-1,0,1};
int agy[]={-1,0,1,0};
int amx[]={0,-1,0,1};
int amy[]={1,0,-1,0};
struct awsl{
	int gx,gy,mx,my,cnt;
};
bool vis[31][31][31][31];
int goalx,goaly;
queue<awsl> q;
bool flag=1;
int main(){
	cin>>n>>m;
	awsl k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>sm[i][j];
			if(sm[i][j]=='G'){
				k.gx=i;
				k.gy=j;
			}
			if(sm[i][j]=='M'){
				k.mx=i;
				k.my=j;
			}
			if(sm[i][j]=='T'){
				goalx=i;
				goaly=j;
			}
		}
	}
	k.cnt=0;
	q.push(k);
	while(!q.empty()){
		awsl tmp,kk;
		tmp=q.front();
		q.pop();
		if(vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]==1)continue;
		vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]=1;
		if(tmp.gx==tmp.mx&&tmp.gx==goalx&&tmp.gy==tmp.my&&tmp.my==goaly){
			cout<<tmp.cnt;
			flag=0;
			break;
		}
		for(int i=0;i<4;i++){
			int new_gx,new_gy,new_mx,new_my;
			new_gx=tmp.gx+agx[i];new_mx=tmp.mx+amx[i];
			new_gy=tmp.gy+agy[i];new_my=tmp.my+amy[i];
			if(sm[new_gx][new_gy]=='X'||sm[new_mx][new_my]=='X'){
				continue;
			}
			if(sm[new_gx][new_gy]=='#'&&sm[new_mx][new_my]!='#'){
				kk.cnt=tmp.cnt+1,kk.gx=tmp.gx,kk.gy=tmp.gy;
				kk.mx=new_mx,kk.my=new_my;
				q.push(kk);
			}
			else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]=='#'){
				kk.cnt=tmp.cnt+1,kk.mx=tmp.mx,kk.my=tmp.my;
				kk.gx=new_gx,kk.gy=new_gy;
				q.push(kk);
			}
			else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]!='#'){
				kk.cnt=tmp.cnt+1,kk.mx=new_mx,kk.my=new_my;
				kk.gx=new_gx,kk.gy=new_gy;
				q.push(kk);
			}
		}
	}
	if(flag)cout<<"no";
	return 0;
}

附封面(四叶漫画和剧场版赢得好啊 ,虽说番的结局还没定

请添加图片描述

赠下图请添加图片描述

请添加图片描述

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

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

相关文章

【点云处理教程】00计算机视觉的Open3D简介

一、说明 Open3D 是一个开源库&#xff0c;使开发人员能够处理 3D 数据。它提供了一组用于 3D 数据处理、可视化和机器学习任务的工具。该库支持各种数据格式&#xff0c;例如 .ply、.obj、.stl 和 .xyz&#xff0c;并允许用户创建自定义数据结构并在程序中访问它们。 Open3D 广…

Python——调用webdriver.Chrome() 报错

今天运行脚本&#xff0c;报错内容如下&#xff1a; collecting ... login_case.py:None (login_case.py) login_case.py:11: in <module> dr webdriver.Chrome() D:\Program Files (x86)\Python\Python39\Lib\site-packages\selenium\webdriver\chrome\webdriver.p…

uniapp使用视频地址获取视频封面

很多时候我们都需要使用视频的第一帧当作视频的封面&#xff0c;今天我们从uni-app的安卓app这个环境来实现下这个需求。 uniapp 安卓APP端&#xff08;ios未测试&#xff09; 方法&#xff1a;使用renderjs实现对DOM元素的操作&#xff0c;创建video元素获取视频转第一帧&am…

图论-简明导读

计算机图论是计算机科学中的一个重要分支&#xff0c;它主要研究图的性质和结构&#xff0c;以及如何在计算机上有效地存储、处理和操作这些图。本文将总结计算机图论的核心知识点。 一、基本概念 计算机图论中的基本概念包括图、节点、边等。图是由节点和边构成的数据结构&am…

APP外包开发的iOS开发框架

在开发APP时需要用到各种框架&#xff0c;这些框架提供了基础的软件功能&#xff0c;可以减轻开发工作量&#xff0c;因此在APP项目开发中熟练运用常见的框架是开发者需要掌握的技能。每个框架都有其特点和适用场景&#xff0c;开发者可以根据项目的需求选择合适的框架进行开发…

kv键值对快速转换为json串(字典类型) | 批量添加双引号

从浏览器中复制的以下数据, 并不能直接使用 refresh:0 start:0 count:20 selected_categories:%7B%7D uncollect:false playable:true tags:在python中需转为字典类型 {refresh: 0,start: 0,count: 20,selected_categories: %7B%7D,uncollect: false,playable: true,tags: , …

docker push 报错:unauthorized: unauthorized to access repository: library/xx处理方法

rootmaster:/home/data/harbor# sudo docker login 49.0.241.2 admin Harbor12345 1.报错原因分析 rootmaster:/home/data/harbor# docker push 49.0.241.2/library/nginx:latest #这种报错 The push refers to repository [49.0.241.2/library/nginx] Get "https://49.…

【网络】网络层(IP协议)

目录 一、基本概念 二、协议头格式 三、网段划分 四、特殊的IP地址 五、IP地址的数量限制 六、私有IP地址和公网IP地址 七、路由 一、基本概念 IP协议&#xff1a;提供一种能力&#xff0c; 将数据从A主机送到B主机&#xff0c;&#xff08;TCP协议&#xff1a;确保IP协议…

数据分析 VS 数据可视化:决战时刻

数据分析和数据可视化是数据科学领域中两个重要的组成部分&#xff0c;很多人不明白两者之间的关系&#xff0c;会误认为是一个东西&#xff0c;其实不然。本文就带大家简单了解一下它们的区别与联系吧&#xff01; 数据分析是指通过收集、处理和解释数据来获取有关特定问题或…

Jenkins 节点该如何管理?

Jenkins 拥有分布式构建(在 Jenkins 的配置中叫做节点)&#xff0c;分布式构建能够让同一套代码在不同的环境(如&#xff1a;Windows 和 Linux 系统)中编译、测试等 Jenkins 的任务可以分布在不同的节点上运行 节点上需要配置 Java 运行时环境&#xff0c;JDK 版本大于 1.5 节…

今年嵌入式行情怎么样?

我不了解其它行业可能描述有些片面&#xff0c;但总的来说&#xff0c;我对嵌入式是很看好的&#xff0c;因为你可以感受到你能实际的做出产品而不是类似前端和互联网只是数字数据。 并且嵌入式的学习过程充满乐趣&#xff0c;你可以接触到从沙子到开关管到逻辑门到芯片架构到…

图文档数字化:实现高效管理的几大步骤

在当今数字化时代&#xff0c;企业越来越意识到数字化管理对于图文档的重要性。传统的纸质文件管理往往效率低下&#xff0c;容易出现丢失和混乱的情况。为了提高工作效率、降低成本并确保数据安全&#xff0c;许多企业选择采用PDM&#xff08;产品数据管理&#xff09;系统来实…

JVM内存模型【入门】

计算机结构简图 JVM内存模型 详细说明&#xff1a;https://blog.csdn.net/m0_71777195/article/details/126247090 什么是JVM&#xff1f; JVM是Java Virtual Machine&#xff08;Java虚拟机&#xff09;的缩写&#xff0c;JVM是一个虚构出来的计算机&#xff0c;有着自己完善…

【触觉智能Purple Pi OH开发板体验】开箱体验:开源主板Purple Pi RK3566 上手指北

前言 前段时间收到来自【电子发烧友】的一款开发板&#xff0c;名叫&#xff1a;PurplePi&#xff0c;216G售价仅249元。它使用的芯片是rk3566&#xff0c;适配的OpenHarmony版本为3.2 Release 是目前最便宜的OpenHarmony标准系统开源开发板&#xff0c;并且软硬件全部开源&am…

SpringCloud之断路器聚合监控

一、Hystrix Turbine简介 看单个的Hystrix Dashboard的数据并没有什么多大的价值&#xff0c;要想看这个系统的Hystrix Dashboard数据就需要用到Hystrix Turbine。Hystrix Turbine将每个服务Hystrix Dashboard数据进行了整合。Hystrix Turbine的使用非常简单&#xff0c;只需要…

QT数据库编程

ui界面 mainwindow.cpp #include "mainwindow.h" #include "ui_mainwindow.h" #include <QButtonGroup> #include <QFileDialog> #include <QMessageBox> MainWindow::MainWindow(QWidget* parent): QMainWindow(parent), ui(new Ui::M…

[Linux]基础IO详解(系统文件I/O接口、文件描述符、理解重定向)

hello&#xff0c;大家好&#xff0c;这里是bang___bang_ &#xff0c;今天和大家谈谈Linux中的基础IO&#xff0c;包含内容有对应的系统文件I/O接口&#xff0c;文件描述符&#xff0c;理解重定向。 目录 1️⃣初识文件 2️⃣ 系统文件I/O接口 &#x1f359;open &#x1…

小程序学习(五):WXSS模板语法

1.什么是WXSS WXSS是一套样式语言,用于美化WXML的组件样式,类似于网页开发中的CSS 2.WXSS和CSS的关系 WXSS模板样式-rpx 3.什么是rpx尺寸单位 4.rpx的实现原理 5.rpx与px之间的单位换算* WXSS模板样式-样式导入 6.什么是样式导入 使用WXSS提供的import语法,可以导入外联的样式…

华为云低代码平台Astro Canvas 搭建汽车展示大屏——实验指导手册

实验背景 大屏应用Astro Canvas是华为云低代码平台Astro的子服务之一&#xff0c;是以数据可视化为核心&#xff0c;以屏幕轻松编排&#xff0c;多屏适配可视为基础&#xff0c;用户可通过图形化界面轻松搭建专业水准的数据可视化大屏。例如汽车展示大屏、监控大屏、项目开发大…

数据结构——绪论

一、绪论 &#xff08;一&#xff09;基本概念 数据&#xff1a;数据是对客观事物的符号表示&#xff0c;在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素&#xff1a;数据元素是数据的基本单位&#xff0c;在计算机程序中通常作为一个整…