2022 The Third J Question Journey

题目链接

Journey

题目大意

Gave us a bunch of intersections,Ask us the least amount of stamina we use to walk from one route to the other,Every time you turn right, you don't need to consume stamina,All other directions are consumption$1$点体力.

题解

理解清楚题意后,Direct double-ended queue search can be done.

代码

#include<iostream>
#include<cstring>
#include<queue>
#include<deque>
#include<map>
using namespace std;
const int maxn = 500010;
#define x first
#define y second
typedef pair<int,int> PII;
int n;
int sx, sy, ex, ey;
int w[maxn][4];
map<PII, int> dist;
typedef struct node
{
    
    int x, y, d;
}Node;
int get_direction(int a, int b)
{
    
    for(int i = 0; i < 4; i ++){
    
        if(w[b][i] == a) {
    
            return (i + 1) % 4;
        }
    }
    return -1;
}
int bfs()
{
    
    deque<Node> q;
    q.push_back({
    sx, sy, 0});
    while(q.size())
    {
    
        auto t = q.front();
        q.pop_front();
        if(t.x == ex && t.y == ey) return t.d;
        int d = get_direction(t.x, t.y);
        for(int i = 0; i < 4; i ++){
    
            int j = w[t.y][i];
            if(j == 0) continue;
            int v = 1;
            if(i == d) v = 0;
            if(!dist.count({
    t.y, j}) || dist[{
    t.y, j}] > t.d + v) {
    
                dist[{
    t.y, j}] = t.d + v;
                if(v == 0) q.push_front({
    t.y, j, dist[{
    t.y, j}]});
                else q.push_back({
    t.y, j, dist[{
    t.y, j}]});
            }
        }
    }
    return -1;
}
int main()
{
    
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
    
        for(int j = 0; j < 4; j ++){
    
            scanf("%d", &w[i][j]);
        }
    }
    scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
    printf("%d\n", bfs());
    return 0;
}

把map换成unordered_mapwill be much faster！

#include<iostream>
#include<cstring>
#include<queue>
#include<deque>
#include<map>
#include<unordered_map>
using namespace std;
const int maxn = 500010;
#define x first
#define y second
typedef pair<int,int> PII;
int n;
int sx, sy, ex, ey;
int w[maxn][4];
unordered_map<int, int> dist[maxn];
typedef struct node
{
    
    int x, y, d;
}Node;
int get_direction(int a, int b)
{
    
    for(int i = 0; i < 4; i ++){
    
        if(w[b][i] == a) {
    
            return (i + 1) % 4;
        }
    }
    return -1;
}
int bfs()
{
    
    deque<Node> q;
    q.push_back({
    sx, sy, 0});
    while(q.size())
    {
    
        auto t = q.front();
        q.pop_front();
        if(t.x == ex && t.y == ey) return t.d;
        int d = get_direction(t.x, t.y);
        for(int i = 0; i < 4; i ++){
    
            int j = w[t.y][i];
            if(j == 0) continue;
            int v = 1;
            if(i == d) v = 0;
            if(!dist[t.y].count(j) || dist[t.y][j]> t.d + v) {
    
                dist[t.y][j] = t.d + v;
                if(v == 0) q.push_front({
    t.y, j, dist[t.y][j]});
                else q.push_back({
    t.y, j, dist[t.y][j]});
            }
        }
    }
    return -1;
}
int main()
{
    
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
    
        for(int j = 0; j < 4; j ++){
    
            scanf("%d", &w[i][j]);
        }
    }
    scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
    printf("%d\n", bfs());
    return 0;
}