当前位置:网站首页>AcWing 1131. 拯救大兵瑞恩 题解(最短路)
AcWing 1131. 拯救大兵瑞恩 题解(最短路)
2022-07-02 18:27:00 【乔大先生】
AcWing 1131. 拯救大兵瑞恩
处理数据非常麻烦的一道题,如何建图记录墙和门,利用set记录门,利用二进制记录钥匙进行匹配,这写操作需要学会记住
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int>PII;
const int N = 15, M = 360, INF = 0x3f3f3f3f;
int h[N * N], ne[M], e[M], w[M], idx; //储存邻接表
int dist[N * N][1 << 11]; //储存状态
deque<PII>q; //储存状态
int n, m, p, k, S;
set<PII>edge; //记录门
int g[N][N];
int dx[4] = {
1, 0, -1, 0};
int dy[4] = {
0, 1, 0, -1};
int key[N * N];
bool st[N * N][1 << 11];
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++ ;
}
void build(){
//建图
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m; j ++ ){
for(int k = 0; k < 4; k ++ ){
int xx = dx[k] + i;
int yy = dy[k] + j;
if(!xx || !yy || xx > n || yy > m) continue; //如果出界,就直接跳过
int a = g[i][j];
int b = g[xx][yy];
if(!edge.count({
a, b})) add(a, b, 0); //如果这个地方没有门,就是一堵墙
}
}
}
}
int bfs(){
memset(dist, 0x3f, sizeof dist);
dist[1][0] = 0; //状态为第一个点,钥匙为0
q.push_back({
1, 0}); //状态为第一个点,钥匙为0
while(q.size()){
auto op = q.front();
q.pop_front();
if(st[op.x][op.y]) continue; //如果这个状态用过
st[op.x][op.y] = true;
if(op.x == n * m) return dist[op.x][op.y];
if(key[op.x]){
//如果这个地方有钥匙
int state = op.y | key[op.x];
if(dist[op.x][state] > dist[op.x][op.y]){
dist[op.x][state] = dist[op.x][op.y];
q.push_front({
op.x, state});
}
}
for(int i = h[op.x]; ~i; i = ne[i]){
int j = e[i];
if(w[i] && !(op.y >> w[i] - 1 & 1)) continue; //如果这里有门但是没钥匙
if(dist[j][op.y] > dist[op.x][op.y] + 1){
//
dist[j][op.y] = dist[op.x][op.y] + 1;
q.push_back({
j, op.y});
}
}
}
return -1;
}
int main()
{
cin>>n>>m>>p>>k;
for(int t = 1, i = 1; i <= n; i ++ ){
for(int j = 1; j <= m; j ++ ){
g[i][j] = t ++ ;
}
}
memset(h, -1, sizeof h);
while(k -- ){
int x1, y1, x2, y2, z;
cin>>x1>>y1>>x2>>y2>>z;
int a = g[x1][y1], b = g[x2][y2];
edge.insert({
a, b}); //记录门或墙
edge.insert({
b, a});
if(z){
add(a, b, z);
add(b, a, z);
}
}
build(); //建图
cin>>S;
while(S -- ){
int a, b, c;
cin>>a>>b>>c;
key[g[a][b]] |= 1 << c - 1; //用二进制存储钥匙
}
cout<<bfs()<<endl;
return 0;
}
边栏推荐
- 预处理和预处理宏
- Juypter notebook modify the default open folder and default browser
- 4274. 后缀表达式-二叉表达式树
- 《架构整洁之道》读书笔记(下)
- ORA-01455: converting column overflows integer datatype
- 【pytorch学习笔记】Tensor
- How to print mybats log plug-in using XML file
- What is the MySQL backup suffix_ MySQL backup restore
- Codeworks 5 questions per day (1700 average) - day 4
- Emmet基础语法
猜你喜欢
新手必看,點擊兩個按鈕切換至不同的內容
Juypter notebook modify the default open folder and default browser
Bubble sort array
《重构:改善既有代码的设计》读书笔记(上)
Processing strategy of message queue message loss and repeated message sending
Tutorial (5.0) 10 Troubleshooting * fortiedr * Fortinet network security expert NSE 5
全志A33使用主线U-Boot
xml开发方式下AutowiredAnnotationBeanPostProcessor的注册时机
Thread application instance
Transformation of thinking consciousness is the key to the success or failure of digital transformation of construction enterprises
随机推荐
机器学习笔记 - 时间序列预测研究:法国香槟的月销量
"Patient's family, please come here" reading notes
Which video recording software is better for the computer
How to print mybats log plug-in using XML file
450-深信服面经1
Getting started with typescript
Gmapping code analysis [easy to understand]
PHP parser badminton reservation applet development requires online system
Idea editor removes SQL statement background color SQL statement warning no data sources are configured to run this SQL And SQL dialect is not config
GMapping代码解析[通俗易懂]
全志A33使用主线U-Boot
PHP非对称加密方法私钥及公钥加密解密的方法
函数高阶-柯里化实现
程序猿入门攻略(十二)——数据的存储
Emmet basic syntax
[test development] software testing - concept
AcWing 343. 排序 题解(floyd性质实现传递闭包)
mybatiesHelperPro工具必须的可以生成到对应项目文件夹下
【pytorch学习笔记】Tensor
Fastdfs installation