Skip to content

14065: 【原4065】泷的旅途

题目

题目描述

author: 郝琰 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4065 

Description

深秋季节,天气渐凉,三叶由于最近期中考试太过忙碌,连续熬夜,不慎染上了感冒。泷听说后,非常担忧,于是决定出发去看三叶。已知泷和三叶处在一个矩形网格上,泷每次可以上下左右移动一格,但是他不能越过边界。要知道,泷虽然擅长体育,但是他的体力毕竟是有限的,已知泷的初始体力为6点,他每移动一格就要耗费一点体力,如果体力耗尽他就不能继续前进。幸运的是,三叶预想到了这一点,于是她提前请人帮忙在一些网格上放置了亲手做的便当。如果泷到达了放有便当的网格,那么他的体力值可以瞬间得到补充,恢复为6。值得注意的是,如果泷到达有便当的网格时体力已经为0,则他连吃饭的力气都没有了,就视为不可到达。如果他到达终点时体力为0,也视为不可到达。已知泷每走一格耗时为1,网格上的有些点上有不可逾越的建筑物,不能通过。

  • 数字 0:建筑物。(不允许通过)
  • 数字 1:空地,泷可以自由行走。
  • 数字 2:泷出发点, 也是一片空地。(行程起点)
  • 数字 3:三叶所在地。(行程终点)
  • 数字 4:便当所在地。

以标号为2的网格为起点,标号为3的网格为终点,问,泷能否见到三叶?如果能, 最短需要多长时间呢?

Input Format

第一行两个数字,网格的行数和列数,n,m。

第2至n+1行,描述整个网格。

Output Format

如果可到达,输出最短用时,否则输出-1。

Sample Input

3 3
2 1 1
1 1 0
1 1 3

Sample Output

4

数据范围

  • 对于70%的数据 0<n,m<=20;
  • 对于30%的数据 0<n,m<=300.

FineArtz's solution

/* 泷的旅途 */
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

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

class Point{
public:
    int x = 0, y = 0, step = 0, hp = 0;
};

int a[310][310];
int v[310][310];
int n, m;
Point st, ed;

inline bool check(const Point &p){
    return (a[p.x][p.y] != 0 && p.hp > v[p.x][p.y]);
}

int bfs(Point s, Point e){
    queue<Point> q;
    q.push(s);
    v[s.x][s.y] = s.hp;
    Point now;
    while (!q.empty()){
        now = q.front();
        q.pop();
        if (a[now.x][now.y] == 4) now.hp = 6;
        if (now.x == e.x && now.y == e.y) return now.step;
        for (int i = 0; i < 4; ++i){
            Point next;
            next.x = now.x + dx[i];
            next.y = now.y + dy[i];
            next.hp = now.hp - 1;
            next.step = now.step + 1;
            if (check(next)){
                v[next.x][next.y] = next.hp;
                q.push(next);
            }
        }
    }
    return -1;
}

int main(){
    memset(a, 0, sizeof(a));
    memset(v, 0, sizeof(v));
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            cin >> a[i][j];
            switch(a[i][j]){
                case 0:
                    v[i][j] = 10;
                    break;
                case 2:
                    st.x = i;
                    st.y = j;
                    break;
                case 3:
                    ed.x = i;
                    ed.y = j;
                    break;
                default:
                    break;
            }
        }
    }
    st.hp = 6;
    cout << bfs(st, ed) << endl;;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cmath"
#include "cstring"
using namespace std;

class position {
public:
    int distance = 0;
    int posx = 0, posy = 0;
    int remain = 0;
};

template <class T>
class my_queue {
    T queue_[100000];
    int start = 0, end = 0;
    int mod = 100000;
public:
    bool empty() const {
        return end - start == 0;
    }
    T front() const {
        return queue_[start % mod];
    }
    void pop() {
        ++start;
    }

    void push(const T& val) {
        queue_[(end++) % mod] = val;
    }
    int size() {
        return end - start;
    }
};

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

my_queue<position> queue_data;
int n, m;
int bfs(int startx, int starty, int endx, int endy) {
    //初始点位
    position start_point;
    start_point.posx = startx;
    start_point.posy = starty;
    start_point.distance = 0;
    start_point.remain = 6;
    queue_data.push(start_point);
    visited[startx][starty] = 6;

    while (!queue_data.empty()) {
        auto temp = queue_data.front();
        queue_data.pop();
        //判断是否到达
        if (temp.posx == endx && temp.posy == endy) {
            return temp.distance;
        }
        //补充能量
        if (map_data[temp.posx][temp.posy] == 4) {
            temp.remain = 6;
            map_data[temp.posx][temp.posy] = 0;
        }
        if (temp.remain > 1) {
            for (int i = 0; i < 4; ++i) {
                auto nextx = temp.posx + dx[i],
                    nexty = temp.posy + dy[i];
                if (nextx >= 0 && nextx < n && nexty >= 0 && nexty < m &&
                    map_data[nextx][nexty]!=0) {
                    position next;
                    next.distance = temp.distance + 1;
                    next.posx = nextx;
                    next.posy = nexty;
                    next.remain = temp.remain - 1;
                    if (next.remain > visited[next.posx][next.posy]) {
                        queue_data.push(next);
                        visited[next.posx][next.posy] = next.remain;
                    }
                }
            }
        }
    }

    return -1;
}

int main() {
    scanf("%d %d", &n, &m);

    int startx = 0, starty = 0,
        endx = 0, endy = 0;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            scanf("%d", &map_data[i][j]);
            if (map_data[i][j] == 2) {
                startx = i, starty = j;
            }
            else if (map_data[i][j] == 3) {
                endx = i, endy = j;
            }
        }

    cout << bfs(startx, starty, endx, endy);

    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
int map[302][302],dis[302][302][7],minx,m,n,sx,sy;
void dfs(int x,int y,int e,int t)
{
    if (t==0) return;
    if (e>minx) return;
    if (map[x][y]==3&&t>0) {
        minx=min(e,minx);
        return;
    }
    if (map[x][y]==4) t=6;
    if (dis[x][y][t]!=0&&e>=dis[x][y][t]) return;
    dis[x][y][t]=e;
    if (map[x-1][y]) dfs(x-1,y,e+1,t-1);
    if (map[x+1][y]) dfs(x+1,y,e+1,t-1);
    if (map[x][y-1]) dfs(x,y-1,e+1,t-1);
    if (map[x][y+1]) dfs(x,y+1,e+1,t-1);
}
int main() {
    cin>>m>>n;
    for (int i=1;i<=m;++i)
        for (int j=1;j<=n;++j) {
            cin >> map[i][j];
            if (map[i][j]==2){
                sx=i;
                sy=j;
            }
        }
    minx=10000000;
    dfs(sx,sy,0,6);
    if (minx<m*n) cout<<minx;
    else cout<<-1;
    return 0;
}

yyong119's solution

#include <cstdio>
#include <queue>
#define MAX_N 305
using namespace std;
struct Node {
    int x, y, cnt;
    Node(int p = 0, int q = 0, int b = 0): x(p), y(q), cnt(b) {
    }
};
const int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m;
int map[MAX_N][MAX_N];
int energy[MAX_N][MAX_N];
queue<Node> q;
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}

int main() {
    n = read(), m = read();
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < m; ++j) {
            map[i][j] = read();
            if (map[i][j] == 2) {
                q.push(Node(i, j, 0));
                energy[i][j] = 6;
            }
        }
    register int i;
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        for (i = 0; i < 4; ++i) {
            int x = cur.x + d[i][0], y = cur.y + d[i][1];
            if (x >= 0 && x < n && y >= 0 && y < m && map[x][y]) {
                // reach destination
                if (map[x][y] == 3) {
                    printf("%d", cur.cnt + 1);
                    return 0;
                }
                // save energy to 6 and not visited
                if (map[x][y] == 4 && !energy[x][y]) {
                    energy[x][y] = 6;
                    q.push(Node(x, y, cur.cnt + 1));
                }
                // map[x][y] can be reached
                // the current solution is better than before that reached [x][y]
                // the energy when reach [x][y] should be at least 2 for further step
                if (map[x][y] == 1 && energy[cur.x][cur.y] - 1 > energy[x][y] && energy[cur.x][cur.y] > 2) {
                    energy[x][y] = energy[cur.x][cur.y] - 1;
                    q.push(Node(x, y, cur.cnt + 1));
                }
            }
        }
    }
    printf("-1");
    return 0;
}