hdu Swipe Bo(bfs+状态压缩)错了多次的题

2024-05-12 20:32
文章标签 bfs 压缩 状态 hdu 多次 bo swipe

本文主要是介绍hdu Swipe Bo(bfs+状态压缩)错了多次的题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Swipe Bo

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1549    Accepted Submission(s): 315


Problem Description
“Swipe Bo” is a puzzle game that requires foresight and skill. 
The main character of this game is a square blue tofu called Bo. We can swipe up / down / left / right to move Bo up / down / left / right. Bo always moves in a straight line and nothing can stop it except a wall. You need to help Bo find the way out.
The picture A shows that we needs three steps to swipe Bo to the exit (swipe up, swipe left, swipe down). In a similar way, we need only two steps to make Bo disappear from the world (swipe left, swipe up)!

Look at the picture B. The exit is locked, so we have to swipe Bo to get all the keys to unlock the exit. When Bo get all the keys, the exit will unlock automatically .The exit is considered inexistent if locked. And you may notice that there are some turning signs, Bo will make a turn as soon as it meets a 

turning signs. For example, if we swipe Bo up, it will go along the purple line.
Now, your task is to write a program to calculate the minimum number of moves needed for us to swipe Bo to the exit.

Input
The input contains multiple cases, no more than 40.
The first line of each test case contains two integers N and M (1≤N, M≤200), which denote the sizes of the map. The next N lines give the map’s layout, with each line containing M characters. A character is one of the following: '#': represents the wall; 'S' represents the start point of the Bo; 'E' represents the exit; '.' represents an empty block; ‘K’ represents the key, and there are no more than 7 keys in the map; 'L','U','D','R' represents the turning sign with the direction of left, up, down, right.

Output
For each test case of the input you have to calculate the minimal amount of moves which are necessary to make Bo move from the starting point to the exit. If Bo cannot reach the exit, output -1. The answer must be written on a single line.

Sample Input
  
5 6 ###### #....# .E...# ..S.## .##### 5 6 ###### #....# .....# SEK.## .##### 5 6 ###### #....# ....K# SEK.## .##### 5 6 ###### #....# D...E# S...L# .#####

Sample Output
  
3 2 7 -1

Source
2013 Multi-University Training Contest 4

题意:有一个迷宫,包含墙、空白格子、起点S、终点E、方向格子(LRUD)和钥匙K。要求如下:

(1)每次转弯只能在碰到墙壁时(每次转弯的选择和初始时从S出发的方向选择均称为一次操作);

(2)对于方向格子,若到达该格子,不管周围是不是墙,必须转向该格子指示的方向(这个不算一次操作);

(3)若迷宫中没有钥匙存在,则求出S到E的最少操作次数;若有钥匙,则必须先遍历到每个钥匙之后才能去E(在这个过程中可以经过E也就是E不算做障碍)。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;const int N  = 225;
const int inf = 1<<29;
struct node{int x,y,sta,stp;
};
int n,m,k;
char mapt[N][N];
int K[N][N];
bool vist[N][N][1<<7];
int dir[4][2]={0,-1,0,1,-1,0,1,0};int judge1(node& now,int &e){int flag=0;if(now.x<0||now.x>=n||now.y<0||now.y>=m)return 0;if(mapt[now.x][now.y]!='#'){if(mapt[now.x][now.y]=='L')e=0,flag=1;else if(mapt[now.x][now.y]=='R')e=1,flag=1;else if(mapt[now.x][now.y]=='U')e=2,flag=1;else if(mapt[now.x][now.y]=='D')e=3,flag=1;else if(mapt[now.x][now.y]=='K')now.sta|=(1<<K[now.x][now.y]);if(flag&&vist[now.x][now.y][now.sta])return 0;else if(flag) vist[now.x][now.y][now.sta]=1;  //固定方向的位置,可以直接标记return 1;}else    //遇到墙,退一格,在当前位置停止{now.x-=dir[e][0];now.y-=dir[e][1];return 2;}}
int bfs(int sx,int sy){queue<node>q;node now,pre;for(int i=0; i<n; i++)for(int j=0; j<m; j++)for(int sta=0; sta<(1<<k); sta++)vist[i][j][sta]=0;now.x=sx,now.y=sy,now.sta=0,now.stp=0;q.push(now);vist[now.x][now.y][now.sta]=1;while(!q.empty()){pre=q.front(); q.pop();pre.stp++;for(int te=0; te<4; te++){int e=te;now=pre;while(1){   //找到一个停止点,或不能走,或走过了,则跳出now.x+=dir[e][0];now.y+=dir[e][1];int flag=judge1(now,e);if(flag==0)break;if(flag==1&&mapt[now.x][now.y]=='E'&&now.sta==(1<<k)-1){return now.stp;}if(flag==2){if(vist[now.x][now.y][now.sta])break;vist[now.x][now.y][now.sta]=1;q.push(now);break;}}}}return -1;
}
int main()
{int sx,sy;while(scanf("%d%d",&n,&m)>0){k=0;for(int i=0; i<n; i++){scanf("%s",mapt[i]);for(int j=0; j<m; j++)if(mapt[i][j]=='S')sx=i,sy=j;else if(mapt[i][j]=='K')K[i][j]=k++;}printf("%d\n",bfs(sx,sy));}
}



这篇关于hdu Swipe Bo(bfs+状态压缩)错了多次的题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/983668

相关文章

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn

MySQL 中的服务器配置和状态详解(MySQL Server Configuration and Status)

《MySQL中的服务器配置和状态详解(MySQLServerConfigurationandStatus)》MySQL服务器配置和状态设置包括服务器选项、系统变量和状态变量三个方面,可以通过... 目录mysql 之服务器配置和状态1 MySQL 架构和性能优化1.1 服务器配置和状态1.1.1 服务器选项

linux进程D状态的解决思路分享

《linux进程D状态的解决思路分享》在Linux系统中,进程在内核模式下等待I/O完成时会进入不间断睡眠状态(D状态),这种状态下,进程无法通过普通方式被杀死,本文通过实验模拟了这种状态,并分析了如... 目录1. 问题描述2. 问题分析3. 实验模拟3.1 使用losetup创建一个卷作为pv的磁盘3.

Python利用PIL进行图片压缩

《Python利用PIL进行图片压缩》有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所以本文为大家介绍了Python中图片压缩的方法,需要的可以参考下... 有时在发送一些文件如PPT、Word时,由于文件中的图片太大,导致文件也太大,无法发送,所有可以对文件中的图

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例

通过prometheus监控Tomcat运行状态的操作流程

《通过prometheus监控Tomcat运行状态的操作流程》文章介绍了如何安装和配置Tomcat,并使用Prometheus和TomcatExporter来监控Tomcat的运行状态,文章详细讲解了... 目录Tomcat安装配置以及prometheus监控Tomcat一. 安装并配置tomcat1、安装

Linux之进程状态&&进程优先级详解

《Linux之进程状态&&进程优先级详解》文章介绍了操作系统中进程的状态,包括运行状态、阻塞状态和挂起状态,并详细解释了Linux下进程的具体状态及其管理,此外,文章还讨论了进程的优先级、查看和修改进... 目录一、操作系统的进程状态1.1运行状态1.2阻塞状态1.3挂起二、linux下具体的状态三、进程的

java中VO PO DTO POJO BO DO对象的应用场景及使用方式

《java中VOPODTOPOJOBODO对象的应用场景及使用方式》文章介绍了Java开发中常用的几种对象类型及其应用场景,包括VO、PO、DTO、POJO、BO和DO等,并通过示例说明了它... 目录Java中VO PO DTO POJO BO DO对象的应用VO (View Object) - 视图对象