题目链接:hdu 4856 Tunnels
题目大意:给定一张图,图上有M个管道,管道给定入口和出口,单向,现在有人想要体验下这M个管道,问最短需要移动的距离,起点未定。
解题思路:首先用bfs处理出两两管道之间移动的距离,然后后用状态压缩求出最短代价,dp[i][j],i表示的已经走过的管道,j是当前所在的管道。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 20;
const int INF = 0x3f3f3f3f;
const int dir[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
struct point {
int x, y;
point (int x = 0, int y = 0) {
this->x = x;
this->y = y;
}
};
struct pipe {
point s, e;
} pi[maxn];
int N, M, d[maxn][maxn];
int dp[(1<<15)+5][maxn];
char g[maxn][maxn];
int bfs (point s, point e) {
int vis[maxn][maxn];
memset(vis, -1, sizeof(vis));
queue<point> que;
vis[s.x][s.y] = 0;
que.push(s);
while (!que.empty()) {
point u = que.front();
que.pop();
if (u.x == e.x && u.y == e.y)
return vis[u.x][u.y];
for (int i = 0; i < 4; i++) {
int x = u.x + dir[i][0];
int y = u.y + dir[i][1];
if (x <= 0 || x > N || y <= 0 || y > N)
continue;
if (vis[x][y] != -1 || g[x][y] == '#')
continue;
vis[x][y] = vis[u.x][u.y] + 1;
que.push(point(x, y));
}
}
return -1;
}
void init () {
for (int i = 1; i <= N; i++)
scanf("%s", g[i] + 1);
memset(d, 0, sizeof(d));
for (int i = 0; i < M; i++) {
scanf("%d%d%d%d", &pi[i].s.x, &pi[i].s.y, &pi[i].e.x, &pi[i].e.y);
for (int j = 0; j < i; j++) {
d[i][j] = bfs(pi[i].e, pi[j].s);
d[j][i] = bfs(pi[j].e, pi[i].s);
}
}
}
int solve () {
memset(dp, INF, sizeof(dp));
for (int i = 0; i < M; i++)
dp[1<<i][i] = 0;
for (int s = 0; s < (1<<M); s++) {
for (int j = 0; j < M; j++) {
if (dp[s][j] == INF)
continue;
for (int k = 0; k < M; k++) {
if (s&(1<<k))
continue;
if (d[j][k] == -1)
continue;
dp[s|(1<<k)][k] = min(dp[s|(1<<k)][k], dp[s][j] + d[j][k]);
}
}
}
int ans = INF;
for (int i = 0; i < M; i++)
ans = min(ans, dp[(1<<M)-1][i]);
return ans == INF ? -1 : ans;
}
int main () {
while (scanf("%d%d", &N, &M) == 2) {
init();
printf("%d\n", solve());;
}
return 0;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
杭电OnlineJudge 200-2099的解题报告
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
acm hdu as easy as a+b
hdu 1695 GCD(欧拉函数+容斥原理).docx
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU 1548 --- basic bfs 2. BNU 1440 --- basic dfs 3. POJ 1190 --- dfs + pruning(Strong) 4. UVALive 2243 --- dfs 5. FZU 2196 --- double bfs 6. PKU 1426 --- bfs + pruning 7. BNU 1038 --- dfs transform 8....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门