BFS+状态压缩 hdu-1885-Key Task

2023-06-28 15:22:08

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1885

题目意思：

给一个矩阵，给一个起点多个终点，有些点有墙不能通过，有些点的位置有门，需要拿到相应颜色的钥匙才能打开，问到达终点的最短步数。

解题思路：

BFS+状态压缩。

将每种颜色对应一个二进制数位，1表示已经得到该颜色的钥匙，0表示没有得到。

一把钥匙可以同种颜色的多扇门。

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/mapmyp1,myp2;bool vis[20][110][110];
char save[110][110];
int n,m,dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};struct Point
{int x,y,step,ss;
}s;bool iscan(int x,int y)
{if(x<1||x>n||y<1||y>m||save[x][y]=='#')return false;return true;
}
//一把钥匙可以开颜色相同的多种锁
void bfs()
{memset(vis,false,sizeof(vis));s.step=0,s.ss=0;queuemyq;myq.push(s);vis[0][s.x][s.y]=true;while(!myq.empty()){Point tmp=myq.front();myq.pop();int xx,yy;for(int i=0;i<4;i++){xx=tmp.x+dir[i][0],yy=tmp.y+dir[i][1];if(!iscan(xx,yy))continue;if(save[xx][yy]=='X'){printf("Escape possible in %d steps.\n",tmp.step+1);return ;}int tt=tmp.ss;if(myp1.find(save[xx][yy])!=myp1.end()) //得到一把钥匙{tt=tt|(1<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

标签：技术

上一篇 > 高清精美壁纸：2013年9月桌面日历壁纸免费下载
下一篇 > [转]C#多线程学习(三) 生产者和消费者

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统微软输入法于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题跑道汽车绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

BFS+状态压缩 hdu-1885-Key Task

相关文章