FZU 2186 小明的迷宫 【压状dp】
2024-08-29 21:26:57
Problem Description
小明误入迷宫,塞翁失马焉知非福,原来在迷宫中还藏着一些财宝,小明想获得所有的财宝并离开迷宫。因为小明还是学生,还有家庭作业要做,所以他想尽快获得所有财宝并离开迷宫。
Input
有多组测试数据。
每组数据第一行给出两个正整数n,m(0<n,m<=100)。代表迷宫的长和宽。
接着n行,每行m个整数。正数代表财宝(财宝的个数不超过10);负数代表墙,无法通过;0代表通道。
每次移动到相邻的格子,所花费的时间是1秒。小明只能按上、下、左、右四个方向移动。
小明的初始位置是(1,1)。迷宫的出口也在(1,1)。
Output
输出获得所有财宝并逃出迷宫所花费的最小时间,如果无法完成目标则输出-1。
Sample Input
3 3 0 0 0 0 100 0 0 0 0 2 2 1 1 1 1
Sample Output
4 4
思路: 发现是一个中国邮递员问题,果断压状
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int dx[]={,,,,-},dy[]={,,-,,};
int a[][],monx[],mony[],n,m,ma[][];
queue<int>qans,qx,qy;
bool visit[][];
int check(int x,int y){
if(x<= || x>n || y<= || y>m || a[x][y]< || visit[x][y])return ;
return ;
}
void bfs(int x,int y,int sc)
{
memset(visit,,sizeof(visit));
int l=,r=;visit[x][y]=;
qx.push(x);qy.push(y);qans.push();
while(!qx.empty())
{
x=qx.front();y=qy.front();
qx.pop();qy.pop();
int ans=qans.front();
qans.pop();
for(int i=;i<=;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(check(xx,yy))continue;
if(a[xx][yy]>)ma[sc][a[xx][yy]]=ans+;
visit[xx][yy]=;
qx.push(xx);qy.push(yy);qans.push(ans+);
}
}
}
int only_one(int k){
if(k-(k & (-k)) == )return ;return ;
}
int dp[][];
int dfs2(int k,int s,int h)
{
if(dp[k][s]!=-)return dp[k][s];
if(only_one(s))return ma[k][];
int ans=0x3f3f3f3f,full = ((<<(h))-) ^ (<<(k-));
for(int i=;i<=h;i++)
if(i != k && ((s & ((<<(i-)))) !=))ans=min(ans,dfs2(i,s & full,h) + ma[k][i]);
return dp[k][s]=ans;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,-,sizeof(dp));
memset(ma,0x3f,sizeof(ma));
int h=,flag=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
if(i== && j==)flag=a[i][j];
if(a[i][j]> || (i== && j==))a[i][j]=++h,monx[h]=i,mony[h]=j;
}
}
for(int i=;i<=h;i++)ma[i][i]=;
for(int i=;i<=h;i++)bfs(monx[i],mony[i],i);
if(flag<)
{
printf("-1\n");continue;
}
int u=dfs2(,(<<h)-,h);
if(u>=0x3f3f3f3f)u=-;
printf("%d\n",u);
}
return ;
}
最新文章
- Sql Server系列:触发器
- 关于Oracle AUTONOMOUS TRANSACTION(自治事务)的介绍
- (转) Artificial intelligence, revealed
- SQL Server编程(02)自定义函数
- 计蒜客 X的平方根
- python: hashlib 加密模块
- Socket重叠IO
- golang语言部分保留字的举例
- 基于spark实现表的join操作
- 局域网yum服务器创建
- poj 2728 Desert King(最小比率生成树,迭代法)
- [数据清洗]- Pandas 清洗“脏”数据(二)
- Eclipse简介和使用技巧快捷方式
- Kafka系列之-Kafka入门
- 【转】Java 线程池
- Linux目录/usr结构说明
- centos 7 增加网卡子接口配置
- js-react组件生命周期
- 【AtCoder】AGC021
- 通过javac导出Jar包
热门文章
- linux下phpstudy的搭建以及网站的搭建
- npm install -g cnpm --registry=https://registry.npm.taobao.org
- 图片,二进制,oracle数据库
- UVA 427 The Tower of Babylon 巴比伦塔(dp)
- 安装linux虚拟机(Ubuntu &; KALI)
- shell脚本自动部署及监控
- websphere7.0异常:SRVE0255E: 尚未定义要处理 /wcm 的 Web 组/虚拟主机
- 计算机应用第七次作业 html制作个人音乐播放站点
- c++ 结构体,设置物品体积并输出物品属性
- tkinter学习-选择按钮