洛谷-P4011 孤岛营救问题
2022/6/11 23:54:11
本文主要是介绍洛谷-P4011 孤岛营救问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
孤岛营救问题
bfs + 状态压缩
对钥匙的状态进行压缩,然后 bfs 剪枝搜索
#include <iostream> #include <cstdio> #include <queue> using namespace std; int dp[20][20][1 << 16 | 1]; int dr[20][20][20][20]; int dor[20][20]; const int xi[4] = {0, 0, 1, -1}; const int yi[4] = {1, -1, 0, 0}; int n, m, p; struct node { int x, y, dis, status; node(){} node(int _x, int _y, int _dis, int _status){x = _x; y = _y; dis = _dis; status = _status;} }; inline bool check(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } int bfs() { int ans = n * m * 100; queue<node>q; q.push({1, 1, 0, dor[1][1]}); while(q.size()) { node now = q.front(); q.pop(); if(now.x == n && now.y == m) { ans = now.dis < ans ? now.dis : ans; continue; } int& dis = dp[now.x][now.y][now.status]; if(dis <= now.dis) continue; dis = now.dis; for(int i=0; i<4; i++) { int xx = now.x + xi[i]; int yy = now.y + yi[i]; if(check(xx, yy)) { int way = dr[now.x][now.y][xx][yy]; if(way == 0 || (way > 0 && (now.status & (1 << way)) == 0)) continue; q.push(node(xx, yy, dis + 1, now.status | dor[xx][yy])); } } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> p; for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) for(int u=0; u<=n; u++) for(int v=0; v<=m; v++) dr[i][j][u][v] = -1; int temp = n * m * 100; for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) for(int u=1<<(p+2); u>=0; u--) dp[i][j][u] = temp; int k; cin >> k; while(k--) { int ax, ay, bx, by, x; cin >> ax >> ay >> bx >> by >> x; dr[ax][ay][bx][by] = x; dr[bx][by][ax][ay] = x; } cin >> k; while(k--) { int x, y, z; cin >> x >> y >> z; dor[x][y] |= 1 << z; } int ans = bfs(); if(ans == temp) ans = -1; cout << ans << endl; return 0; }
这篇关于洛谷-P4011 孤岛营救问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了