题意:
悟空要救唐僧,中途有最多就把钥匙,和最多五条蛇,要求就得唐僧并且拿到所有种类的钥匙(两个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 状态压缩广搜的更多相关文章
-
POJ1324贪吃蛇(状态压缩广搜)
题意: 给你一个地图,有的地方能走,有的地方不能走,然后给你一条蛇,问你这条蛇的头部走到1,1的位置的最少步数,注意,和贪吃蛇不太一样,就是蛇咬到自己身体的那个地方,具体怎么不一样自己模拟 ...
-
UVA 10047 The Monocycle (状态记录广搜)
Problem A: The Monocycle A monocycle is a cycle that runs on one wheel and the one we will be consi ...
-
UVa 10047 自行车 状态记录广搜
每个格子(x,y,drection,color) #include<iostream> #include<cstdio> #include<cstring> #in ...
-
POJ2688状态压缩(可以+DFS剪枝)
题意: 给你一个n*m的格子,然后给你一个起点,让你遍历所有的垃圾,就是终点不唯一,问你最小路径是多少? 思路: 水题,方法比较多,最省事的就是直接就一个BFS状态压缩暴搜就行 ...
-
hdu 5025 Saving Tang Monk 状态压缩dp+广搜
作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4092939.html 题目链接:hdu 5025 Saving Tang Monk 状态压缩 ...
-
hdu 5094 Maze 状态压缩dp+广搜
作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4092176.html 题目链接:hdu 5094 Maze 状态压缩dp+广搜 使用广度优先 ...
-
Oj 24260: Lilypad Pond (神奇广搜题,状态搜索)
题目 为了让奶牛们娱乐和锻炼,约翰建造了一个美丽的池塘.这个池塘是矩形的,可以分成M×N个方格.一些格子是坚固得令人惊讶的莲花,还有一些是岩石,其余的只是美丽,纯净,湛蓝的水.贝西正在练习芭蕾舞,她站 ...
-
魔板 Magic Squares(广搜,状态转化)
题目背景 在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板.这是一张有8个大小相同的格子的魔板: 1 2 3 4 8 7 6 5 题目描述 我们知道魔板的每一个方格都有一种颜色.这8种颜 ...
-
【宽度优先搜索】神奇的状态压缩 CodeVs1004四子连棋
一.写在前面 其实这是一道大水题,而且还出在了数据最水的OJ上,所以实际上这题并没有什么难度.博主写这篇blog主要是想写下一个想法--状态压缩.状态压缩在记录.修改状态以及判重去重等方面有着极高的( ...
随机推荐
-
Security &#187; Authorization &#187; 基于资源的授权
Resource Based Authorization¶ 基于资源的授权 68 of 73 people found this helpful Often authorization depends ...
-
Android Handler 避免内存泄漏的用法总结
Android开发经常会用到handler,但是我们发现每次使用Handler都会出现:This Handler class should be static or leaks might occur ...
-
js中关于string的一些常用的方法
最近总结了一些关于string中的常用方法, 其中大部分的方法来自于<JavaScript框架设计>这本书, 如果有更好的方法,或者有关于string的别的常用的方法,希望大家不吝赐教. ...
-
WebApi 方法的参数类型总结。
1:[HttpGet] ①:get方法之无参数. [HttpGet] public IHttpActionResult GetStudentInfor() { List<StudentMode ...
-
c++ 开源库介绍和安装
1 BLAS库 BLAS(Basic Linear Algebra Subprograms)是一组线性代数计算中通用的基本运算操作函数集合.BLAS Technical (BLAST) Forum负责 ...
-
lumen----------lumen如何安装和使用redis第三方包扩展
1. 安装扩展 要使用redis必须安装两个扩展 "predis/predis": "~1.0", "illuminate/redis" ...
-
mysqli链接数据库
<?php $uid = $_GET['uid']; $host = 'localhost';$database = 'test';$username = 'root';$password = ...
-
<;转>;jmeter(二十一)jmeter常用插件介绍
本博客转载自:http://www.cnblogs.com/imyalost/category/846346.html 个人感觉不错,对jmeter讲解非常详细,担心以后找不到了,所以转发出来,留着慢 ...
-
<;构建之法>;8,9,10章的读后感
第八章 这一章主要讲的是需求分析,主要介绍在客户需求五花八门的情况下,软件团队如何才能准确而全面地找到这些需求. 第九章 问题:我们现在怎样培养才能成为一名合格的PM呢? 第十章 问题:如果典型用户吴 ...
-
linux平台模拟生成CAN设备
前言 使用socketCan的过程中有时候没有can接口设备,但是需要测试一下can接口程序是否有问题, 此时需要系统模拟生成can设备,本文介绍linux平台模拟生成CAN设备的方法. 实现步骤 1 ...