首页 > 代码库 > Gym - 101291C (很有意思的最短路）
Gym - 101291C (很有意思的最短路）
题意：
给出一张地图和机器人还有出口的位置，地图上面有障碍。然后给出UDLR上下左右四种指令，遇到障碍物或者越界的指令会忽略，剩下的继续执行。
只要到达出口就算找到出口，然后给你一串指令，让你修改指令达到出口，删除或插入任意一个指令花费为1，问让机器人能够找到出口所花费最少。
思路：
感觉很有意思的一道最短路，思路是把每个点分成变成指令长度个点+1，然后就相当于有n^3个点。然后指令是顺序执行的，所以当前点的状态最多到达
周围可到达点的同一状态。所以我们就可以建边，如果我们走到隔壁点的当前状态就相当于插入了一个指令，就当前点到隔壁点建条花费为1的边。还可以建立
当前点到当前点的下个状态的边，花费为1，相当于删除当前指令。
这道题WA了很久= =然后找到数据对拍，最后发现是因为少建了一种边，就是指令执行完了，然后走向下一个点指令执行完了的边没有建立。
代码：
/** @xigua */
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <climits>
#include <bitset>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 1e8 + 5;
const ll inf = 1e15 + 5;
const db eps = 1e-6;
char mapp[55][55], op[55];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, m;
int cnt, head[maxn], dis[maxn];
struct Edge {
int v, w, next;
bool operator < (const Edge &rhs) const {
return w > rhs.w;
}
} e[maxn*5];
void add(int u, int v, int co) {
e[cnt].v = v;
e[cnt].w = co;
e[cnt].next = head[u];
head[u] = cnt++;
}
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
void dij(int s, int len) {
priority_queue<Edge> pq;
for (int i = 1; i <= len; i++)
dis[i] = INF;
bool vis[maxn] = {0};
dis[s] = 0;
pq.push((Edge){s, 0});
while (!pq.empty()) {
Edge tmp = pq.top(); pq.pop();
if (vis[tmp.v]) continue;
vis[tmp.v] = 1;
for (int i = head[tmp.v]; ~i; i = e[i].next) {
Edge u = e[i];
if (dis[u.v] > dis[tmp.v] + u.w) {
dis[u.v] = dis[tmp.v] + u.w;
pq.push((Edge){u.v, dis[u.v]});
}
}
}
}
bool safe(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m && mapp[x][y] != ‘#‘;
}
void solve() {
while (cin >> n >> m) {
init();
for (int i = 1; i <= n; i++)
scanf("%s", mapp[i] + 1);
scanf("%s", op+1);
int len = strlen(op + 1);
int st, ed;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mapp[i][j] == ‘R‘) st = (i - 1) * m + j;
if (mapp[i][j] == ‘E‘) ed = (i - 1) * m + j;
if (mapp[i][j] == ‘#‘) continue;
for (int k = 1; k <= len; k++) {
for (int p = 0; p < 4; p++) {
int x = i + dx[p];
int y = j + dy[p];
if (safe(x, y)) {
int u = ((i - 1) * m + j) * (len + 1) + k;
int v = ((x - 1) * m + y) * (len + 1) + k;
add(u, v, 1);
}
}
int x = i, y = j;
if (op[k] == ‘R‘) y++;
else if (op[k] == ‘L‘) y--;
else if (op[k] == ‘U‘) x--;
else x++;
if (safe(x, y)) {
int u = ((i - 1) * m + j) * (len + 1) + k;
int v = ((x - 1) * m + y) * (len + 1) + k + 1;
add(u, v, 0);
}
else {
int u = ((i - 1) * m + j) * (len + 1) + k;
add(u, u + 1, 0);
}
int u = ((i - 1) * m + j) * (len + 1) + k;
add(u, u + 1, 1);
}
/* 就是这里 没有考虑到建立边 */
for (int p = 0; p < 4; p++) {
int x = i + dx[p];
int y = j + dy[p];
if (safe(x, y)) {
int u = ((i - 1) * m + j) * (len + 1) + len + 1;
int v = ((x - 1) * m + y) * (len + 1) + len + 1;
add(u, v, 1);
}
}
}
}
dij(st * (len + 1) + 1, (n * m + 1) * (len + 1));
int ans = INF;
for (int i = 1; i <= len + 1; i++) {
int cur = ed * (len + 1) + i;
ans = min(ans, dis[cur]);
}
cout << ans << endl;
}
}
int main() {
int t = 1, cas = 1;
//freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//scanf("%d", &t);
while (t--) {
// printf("Case %d: ", cas++);
solve();
}
return 0;
}
Gym - 101291C (很有意思的最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。