Skip to content

14284: 【原4284】吉良吉影的平静生活

题目

题目描述

author: dhc 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4284

问题描述

吉良吉影,33岁,未婚,在龟友连锁超市工作,过着平静的生活。 龟友连锁超市可以看作一个$n \times n$的网格,左上角为$(1,1)$,右下角为$(n,n)$。一些位置是过道,一些位置是不可通行的货架,还有一些位置是成对的传送带(编号为$1, 2, \cdots$,有传送带的位置也可以正常通行)。 吉良吉影可以花费一个单位的时间从一格移动到上下左右相邻的一格,也可以花费一个单位的时间从传送带的一侧移到另一侧。 现在他需要从$(s_x,s_y)$移动到$(t_x,t_y)$(保证起点和终点可达),由于想要尽快下班回家,所以他想要知道,所需要的时间最短是多少?

输入格式

第一行五个整数,$n, s_x, s_y, t_x, t_y$。 接下来$n$行,每行$n$个数字,第$i$行第$j$个数字$a_{ij}$表示超市$(i,j)$位置的情况:

  • 若$a_{ij} = 0$,代表$(i,j)$位置可以通行;
  • 若$a_{ij} = -1$,代表$(i,j)$位置不可以通行;
  • 若$a_{ij} = a_{kl} > 0$,代表$(i,j)$位置和$(k,l)$位置之间有一个传送带。

输出格式

共一行一个整数,表示最短需要的时间。

样例输入1

3 1 1 1 3
0 -1 0
0 -1 0
0 0 0

样例输出1

6

样例输入2

3 1 1 1 3
0 -1 0
1 -1 1
2 -1 2

样例输出2

3

数据范围与约束

对于40%的数据,$n \le 10$,且没有传送带。 对于100%的数据,$n \le 200$,传送带的数量少于10个。

ligongzzz's solution

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<vector<int>> map_data;
map<int,vector<pair<int,int>>> ele_data;
int n, sx, sy, tx, ty;

int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };

int bfs() {
    queue <pair<pair<int, int>, int>> qdata;
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    qdata.push(make_pair(make_pair(sx, sy), 0));
    visited[sx][sy] = true;

    while (!qdata.empty()) {
        auto temp = qdata.front();
        qdata.pop();
        if (temp.first.first == tx && temp.first.second == ty) {
            return temp.second;
        }
        int cx = temp.first.first, cy = temp.first.second;
        for (int i = 0; i < 4; ++i) {
            int nx = temp.first.first + dx[i], ny = temp.first.second + dy[i];
            if (nx < n && ny < n && nx >= 0 && ny >= 0 && !visited[nx][ny] && map_data[nx][ny] >= 0) {
                qdata.push(make_pair(make_pair(nx, ny), temp.second + 1));
                visited[nx][ny] = true;
            }
        }
        if (map_data[cx][cy] > 0) {
            int nx, ny;
            if (ele_data[map_data[cx][cy]][0].first == cx && ele_data[map_data[cx][cy]][0].second == cy) {
                nx = ele_data[map_data[cx][cy]][1].first;
                ny = ele_data[map_data[cx][cy]][1].second;
            }
            else {
                nx = ele_data[map_data[cx][cy]][0].first;
                ny = ele_data[map_data[cx][cy]][0].second;
            }
            if (!visited[nx][ny]) {
                qdata.push(make_pair(make_pair(nx, ny), temp.second + 1));
                visited[nx][ny] = true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> sx >> sy >> tx >> ty;
    --sx, --sy, --tx, --ty;

    map_data.resize(n, vector<int>(n));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> map_data[i][j];
            if (map_data[i][j] > 0) {
                if (ele_data.find(map_data[i][j]) == ele_data.end()) {
                    ele_data.insert(make_pair(map_data[i][j], vector<pair<int, int>>(1, make_pair(i, j))));
                }
                else {
                    ele_data[map_data[i][j]].emplace_back(make_pair(i, j));
                }
            }
        }
    }

    cout << bfs();

    return 0;
}