首页 > 代码库 > hdu 4856 Tunnels (bfs + 状压dp)
hdu 4856 Tunnels (bfs + 状压dp)
题目链接
题意:
一个边长为n的正方形网格图，其中有一些点‘ . ‘表示可达，‘ # ‘表示不可达，你不能走到不可达的点上，以及每一个单位时间你只能走到相邻的网格（上下左右）。现在给你m条密道，每条密道起始位置(x1,y1)，终点位置(x2,y2)，当你从起点进去后能瞬间从终点位置出来（不花时间），但是每条密道你只能走一遍。现在，你可以选择任意一个可达的点作为起点，问能否在满足条件下走完所有的密道，有解输出最短时间，否则输出-1。
分析：
先用bfs处理出来每个隧道之间的距离，然后就是走的各个隧道之间的顺序，可以用状压dp来做，
dp[ i ][ j ]表示已经经过的密道状态为 i （i为压缩状态，二进制的每一位表示相应的密道是否已经走过，走过为1，否则为0），最后一个经过的密道是j时的最小用时。
状态转移方程为：dp[ i | ( 1 << k ) ][ k ] = min { dp[ i | ( 1 << k ) ][ k ] , dp[ i ][ j ] + dist[ j ][ k ] } 。
其中必须保证dp[ i ][ j ]已经有了的状态，dist[ j ][ k ]不是INF ( j 出发能到达 k )，以及状态 i 中不包含第 k 个密道能才发生转移。
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <queue> 5 #include <cstring> 6 #include <cstdlib> 7 #include <algorithm> 8 #define LL __int64 9 const int maxn = 20+10;10 using namespace std;11 const int INF = 1<<28;12 char s[maxn][maxn];13 int c[maxn][maxn], d[1<<17][20], n;14 int dx[] = {0, 0, 1, -1};15 int dy[] = {1, -1, 0, 0};16 struct node17 {18 int x, y, step;19 }pos, ne;20 int bfs(int a, int b, int c, int d)21 {22 queue<node>q;23 int vis[maxn][maxn], i;24 memset(vis, 0, sizeof(vis));25 ne.x = a; ne.y = b; ne.step = 0;26 vis[a][b] = 1;27 q.push(ne);28 while(!q.empty())29 {30 pos = q.front();31 q.pop();32 if(pos.x == c && pos.y == d)33 return pos.step;34 for(i = 0; i < 4; i++)35 {36 ne.x = pos.x+dx[i];37 ne.y = pos.y+dy[i];38 ne.step = pos.step+1;39 if(!(ne.x>=1&&ne.x<=n && ne.y>=1&&ne.y<=n)) continue;40 if(s[ne.x][ne.y]==‘#‘) continue;41 if(vis[ne.x][ne.y]) continue;42 q.push(ne);43 vis[ne.x][ne.y] = 1;44 }45 }46 return INF;47 }48 int main()49 {50 int m, i, j, k, ans;51 int x1[maxn], y1[maxn], x2[maxn], y2[maxn];52 while(~scanf("%d%d", &n, &m))53 {54 memset(c, 0, sizeof(c));55 memset(s, 0, sizeof(s));56 for(i = 1; i <= n; i++)57 {58 getchar();59 for(j = 1; j <= n; j++)60 scanf("%c", &s[i][j]);61 }62 for(i = 0; i < m; i++)63 cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];64 for(i = 0; i < m; i++)65 for(j = 0; j < m; j++)66 {67 if(i == j) continue;68 c[i][j] = bfs(x2[i], y2[i], x1[j], y1[j]);69 }70 for(i = 0; i < (1<<m); i++)71 for(j = 0; j < m; j++)72 d[i][j] = INF;73 74 for(i = 0; i < m; i++)75 d[1<<i][i] = 0;76 77 for(i = 0; i < (1<<m); i++)78 for(j = 0; j < m; j++)79 if(d[i][j]!=INF)80 for(k = 0; k < m; k++)81 {82 if(!(i&(1<<k)) && c[j][k]!=INF)83 d[i|(1<<k)][k] = min(d[i|(1<<k)][k], d[i][j]+c[j][k]);84 }85 ans = INF;86 for(i = 0; i < m; i++)87 ans = min(ans, d[(1<<m)-1][i]);88 if(ans == INF) printf("-1\n");89 else90 printf("%d\n", ans);91 }92 return 0;93 }
hdu 4856 Tunnels (bfs + 状压dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。