最短时间-逃出生天

【编程题目 |200分】最短时间 逃出生天【2021考试题】

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，

编码后请点击”保存并调试“按钮进行代码提交。

■ 题目描述

• 在大小为 row*col 的方格区域地图上，地图上每一个格子均有一个倒计时转置，当时间变为0时会触发机关，使得该格子区域变为一处死地，该区域无法通过，英雄每移动一个格子消耗1s。
• 英雄可以上下左右四个方向移动，请设置一条最佳路线，让英雄最短时间从[0,0]到达[row-1,col-1]离开。
• 注意：英雄在出生点和出口时，该区域不能为死地。

输入

• 首行输入单个空格分隔的两个正整数row和col，row代表行数，col代表列数。
• 接下来row行，每一行包含col个以当个空格分隔的数字，代表对应时间的区域倒计时装置设定时间time，单位为秒。

输出

• 英雄从起点到终点的最短用时，若无法到达，则输出-1。

C++ BFS解法

#include<bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int row, col;

class Node {
public:
    int x;
    int y;
    int step;

    Node(int x_, int y_, int step_) {
        this->x = x_;
        this->y = y_;
        this->step = step_;
    }
};

bool inGrid(int x, int y)
{
    return x >= 0 && x < row && y >= 0 && y < col;
}

剩余50%内容，购买单篇文章或订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接