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使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

关于WebSocket协议状态码解析

《关于WebSocket协议状态码解析》:本文主要介绍关于WebSocket协议状态码的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录WebSocket协议状态码解析1. 引言2. WebSocket协议状态码概述3. WebSocket协议状态码详解3

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

一文详解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.