题目链接
题目简述
一个 (n imes m) 的矩阵，每个单元位置用一个有序数对（行号，列号）表示。
上下左右四个方向相邻的两个单元格之间存在一下情况：
-
直接相连
-
符合某种条件的情况下相连
-
不相连
其中某种条件分为 (p) 类要素，使一种条件成立的要素相同，不同条件成立的要素不同。
初始位置为 ((1,1)) ，问如何以最少步数到达 ((n,m)) 。
解题思路
数据范围这么友好，不暴力怎么对得起出题人呢？？/jk
考虑定义
-
一个四维数组表示 ((x_1,y_1) o (x_2,y_2)) 是否符合条件相连通。
-
(vis[i][j][k]) 表示条件要素为 (k) 的情况下，((i,j)) 位置是否已经查找过。
-
(key[i][j]) 表示第 (key) 类要素需要在 ((i,j)) 单元获取。
这里用用到状态压缩存储条件要素。（不会状压的请去睡觉）
然后，然后就可以直接枚举 (DFS) 了。（不会 (DFS) 搜最短路径的请去睡觉）
小小优化
定义结构体记录单元（行号，列号，满足的条件，到该单元的最小花费），用队列存储（将路径记录下来），减少枚举数量。
友情提示
-
钥匙质量不错，不是一次性的
woc -
钥匙做工不错，一个单元可以放多把钥匙
woc -
初始点好像并没有说不能放钥匙
woc -
输出 (-1) 赞~
-
(DFS) 不加
return可以卡掉五个测试点。。。（然后 (debug) 了一下午）
CODE
/*
Name: #6121. 「网络流 24 题」孤岛营救问题
Solution: 最短路
By Frather_
*/
#include <iostream>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
// #include <map>
#include <stack>
#define ll long long
#define InF 0x7fffffff
#define kMax 10e5
#define kMin -10e5
#define kMod 998244353
#define kMod2 19260817
#define kMod3 19660813
#define base 1331
using namespace std;
/*=========================================快读*/
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
/*=====================================定义变量*/
int n, m, p;
int k;
int s;
int map[20][20][20][20], key[20][20];
struct node
{
int x, y;
int key;
int dis;
};
bool vis[20][20][1 << 11];
queue<node> q;
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
int ans = -1;
/*===================================自定义函数*/
void bfs()
{
q.push((node){1, 1, 0 | key[0][0], 0}); //初始化第一个位置
vis[1][1][0 | key[1][1]] = true;
while (!q.empty())
{
node now = q.front(), next;
q.pop();
for (int i = 1; i <= 4; i++)
{
next.x = now.x + dx[i];
next.y = now.y + dy[i];
if (next.x < 1 || next.x > n || next.y < 1 || next.y > m || !map[now.x][now.y][next.x][next.y]) //若dfs越界或者该两单元间不存在可通路（即有“一堵不可逾越的墙”），跳过
continue;
if ((map[now.x][now.y][next.x][next.y] == -1) || (now.key & map[now.x][now.y][next.x][next.y]))
{
if (!key[next.x][next.y])
next.key = now.key;
else
next.key = now.key | key[next.x][next.y];
if (vis[next.x][next.y][next.key])
continue;
vis[next.x][next.y][next.key] = true;
next.dis = now.dis + 1;
q.push(next);
if (next.x == n && next.y == m)
{
ans = next.dis;
return;
}
}
}
}
}
/*=======================================主函数*/
int main()
{
n = read();
m = read();
p = read();
k = read();
memset(map, -1, sizeof(map));
for (int i = 1; i <= k; i++)
{
int x_1 = read();
int y_1 = read();
int x_2 = read();
int y_2 = read();
int g = read();
map[x_1][y_1][x_2][y_2] = g ? 1 << g - 1 : g;
map[x_2][y_2][x_1][y_1] = map[x_1][y_1][x_2][y_2];
}
s = read();
for (int i = 1; i <= s; i++)
{
int x = read();
int y = read();
int g = read();
key[x][y] |= 1 << g - 1;
}
bfs();
printf("%d
", ans);
return 0;
}
最后
感谢阅读，留个点赞谢谢~