hdu5025 状态压缩广搜

时间:2022-03-03 11:16:31

题意:

      悟空要救唐僧,中途有最多就把钥匙,和最多五条蛇,要求就得唐僧并且拿到所有种类的钥匙(两个1只拿一个就行),拿钥匙i之前必须拿到钥匙i-1,打蛇多花费一秒,问救出唐僧并且拿到所有种类的钥匙的最小花费时间。

思路:

      应该两种方法吧,感觉很多都是用4维的标记,然后广搜的,我用的是3维的标记,然后优先队列广搜的,题目没啥难的,关键是读懂题,敲代码的时候细心点就行了。mark[x][y][key] 表示在x,y点是要是状态是key是否走过。


#include<stdio.h>
#include<string.h>
#include<queue> #define N 110

using namespace
std; typedef struct NODE
{
int
x ,y ,key ,t;
int
she;
friend bool operator < (
NODE a ,NODE b)
{
return
a.t > b.t;
}
}
NODE; NODE xin ,tou;
int
mark[N][N][1<<10];
int
Map[N][N];
int
dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
int
ex ,ey ,n ,M; int BFS(int x ,int y)
{

priority_queue<NODE>q;
xin.x = x ,xin.y = y ,xin.t = 0 ,xin.key = 0 ,xin.she = 0;
memset(mark ,0 ,sizeof(mark));
mark[xin.x][xin.y][xin.key] = 1;
q.push(xin);
while(!
q.empty())
{

tou = q.top();
q.pop();
if(
tou.x == ex && tou.y == ey && tou.key == (1 << M) - 1)
{
return
tou.t;
}
for(int
i = 0 ;i < 4 ;i ++)
{

xin.x = tou.x + dir[i][0];
xin.y = tou.y + dir[i][1];
xin.t = tou.t + 1;
if(
xin.x < 1 || xin.x > n || xin.y < 1 || xin.y > n || !Map[xin.x][xin.y])
continue;
if(
Map[xin.x][xin.y] >= 11)
{
if(
tou.she & (1 << (Map[xin.x][xin.y] - 1)))
xin.she = tou.she;
else
{

xin.she = tou.she | (1 << (Map[xin.x][xin.y] - 1));
xin.t ++;
}
}
else
xin.she = tou.she;
if(
Map[xin.x][xin.y] >= 1 && Map[xin.x][xin.y] <= 9)
{
if(
Map[xin.x][xin.y] != 1 && !(tou.key & (1 << (Map[xin.x][xin.y] - 2))))
xin.key = tou.key;
else

xin.key = tou.key | (1 << (Map[xin.x][xin.y] - 1));
}
else
xin.key = tou.key;
if(!
mark[xin.x][xin.y][xin.key])
{

mark[xin.x][xin.y][xin.key] = 1;
q.push(xin);
}
}
}
return -
1;
} int main ()
{
int
i ,j ,x ,y;
char
str[N];
while(~
scanf("%d %d" ,&n ,&M) && n + M)
{
int
ss = 0;
for(
i = 1 ;i <= n ;i ++)
{

scanf("%s" ,str);
for(
j = 0 ;j < n ;j ++)
{
if(
str[j] == 'K')
{

x = i ,y = j + 1;
Map[x][y] = 10;
}
if(
str[j] == 'T')
{

ex = i ,ey = j + 1;
Map[ex][ey] = 10;
}
if(
str[j] == '.')
Map[i][j+1] = 10;
if(
str[j] == '#')
Map[i][j+1] = 0;
if(
str[j] >= '1' && str[j] <= '9')
Map[i][j+1] = str[j] - '0';
if(
str[j] == 'S')
{

ss++;
Map[i][j+1] = 10 + ss;
}
}
}
int
Ans = BFS(x ,y);
if(
Ans == -1) puts("impossible");
else
printf("%d\n" ,Ans);
}
return
0;
}





hdu5025 状态压缩广搜的更多相关文章

  1. POJ1324贪吃蛇(状态压缩广搜)

    题意:       给你一个地图,有的地方能走,有的地方不能走,然后给你一条蛇,问你这条蛇的头部走到1,1的位置的最少步数,注意,和贪吃蛇不太一样,就是蛇咬到自己身体的那个地方,具体怎么不一样自己模拟 ...

  2. UVA 10047 The Monocycle (状态记录广搜&rpar;

    Problem A: The Monocycle  A monocycle is a cycle that runs on one wheel and the one we will be consi ...

  3. UVa 10047 自行车 状态记录广搜

    每个格子(x,y,drection,color) #include<iostream> #include<cstdio> #include<cstring> #in ...

  4. POJ2688状态压缩(可以&plus;DFS剪枝)

    题意:       给你一个n*m的格子,然后给你一个起点,让你遍历所有的垃圾,就是终点不唯一,问你最小路径是多少? 思路:       水题,方法比较多,最省事的就是直接就一个BFS状态压缩暴搜就行 ...

  5. hdu 5025 Saving Tang Monk 状态压缩dp&plus;广搜

    作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4092939.html 题目链接:hdu 5025 Saving Tang Monk 状态压缩 ...

  6. hdu 5094 Maze 状态压缩dp&plus;广搜

    作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4092176.html 题目链接:hdu 5094 Maze 状态压缩dp+广搜 使用广度优先 ...

  7. Oj 24260&colon; Lilypad Pond &lpar;神奇广搜题,状态搜索)

    题目 为了让奶牛们娱乐和锻炼,约翰建造了一个美丽的池塘.这个池塘是矩形的,可以分成M×N个方格.一些格子是坚固得令人惊讶的莲花,还有一些是岩石,其余的只是美丽,纯净,湛蓝的水.贝西正在练习芭蕾舞,她站 ...

  8. 魔板 Magic Squares(广搜,状态转化)

    题目背景 在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板.这是一张有8个大小相同的格子的魔板: 1 2 3 4 8 7 6 5 题目描述 我们知道魔板的每一个方格都有一种颜色.这8种颜 ...

  9. 【宽度优先搜索】神奇的状态压缩 CodeVs1004四子连棋

    一.写在前面 其实这是一道大水题,而且还出在了数据最水的OJ上,所以实际上这题并没有什么难度.博主写这篇blog主要是想写下一个想法--状态压缩.状态压缩在记录.修改状态以及判重去重等方面有着极高的( ...

随机推荐

  1. Security &&num;187&semi; Authorization &&num;187&semi; 基于资源的授权

    Resource Based Authorization¶ 基于资源的授权 68 of 73 people found this helpful Often authorization depends ...

  2. Android Handler 避免内存泄漏的用法总结

    Android开发经常会用到handler,但是我们发现每次使用Handler都会出现:This Handler class should be static or leaks might occur ...

  3. js中关于string的一些常用的方法

    最近总结了一些关于string中的常用方法, 其中大部分的方法来自于<JavaScript框架设计>这本书, 如果有更好的方法,或者有关于string的别的常用的方法,希望大家不吝赐教. ...

  4. WebApi 方法的参数类型总结。

    1:[HttpGet]  ①:get方法之无参数. [HttpGet] public IHttpActionResult GetStudentInfor() { List<StudentMode ...

  5. c&plus;&plus; 开源库介绍和安装

    1 BLAS库 BLAS(Basic Linear Algebra Subprograms)是一组线性代数计算中通用的基本运算操作函数集合.BLAS Technical (BLAST) Forum负责 ...

  6. lumen----------lumen如何安装和使用redis第三方包扩展

    1. 安装扩展 要使用redis必须安装两个扩展 "predis/predis": "~1.0",   "illuminate/redis" ...

  7. mysqli链接数据库

    <?php $uid = $_GET['uid']; $host = 'localhost';$database = 'test';$username = 'root';$password = ...

  8. &lt&semi;转&gt&semi;jmeter(二十一)jmeter常用插件介绍

    本博客转载自:http://www.cnblogs.com/imyalost/category/846346.html 个人感觉不错,对jmeter讲解非常详细,担心以后找不到了,所以转发出来,留着慢 ...

  9. &lt&semi;构建之法&gt&semi;8&comma;9&comma;10章的读后感

    第八章 这一章主要讲的是需求分析,主要介绍在客户需求五花八门的情况下,软件团队如何才能准确而全面地找到这些需求. 第九章 问题:我们现在怎样培养才能成为一名合格的PM呢? 第十章 问题:如果典型用户吴 ...

  10. linux平台模拟生成CAN设备

    前言 使用socketCan的过程中有时候没有can接口设备,但是需要测试一下can接口程序是否有问题, 此时需要系统模拟生成can设备,本文介绍linux平台模拟生成CAN设备的方法. 实现步骤 1 ...