寻宝任务"/>
I:寻宝任务
题目链接:I-寻宝任务_“学佳澳杯”湖北文理学院第一届程序设计竞赛 (nowcoder.com)
方法:BFS+优先队列(大根堆)
具体看代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;int n, m, x, y, t;
int num[505][505];
bool vis[505][505];
int D[9][2] = {{0, 0}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};struct Node{int a, b, g;bool operator<(const Node &tmp) const{//便于大根堆的排序规则return g < tmp.g;}
};void solve(){cin >> n >> m >> x >> y >> t;for (int i = 1; i <= n; i++)//初始化地图for (int j = 1; j <= m; j++)cin >> num[i][j];priority_queue<Node> q;q.push({x, y, t});int ans = 0;while (!q.empty()){//BFSauto [x, y, hp] = q.top();q.pop();if (vis[x][y]) continue;//如果访问就continuevis[x][y] = true;//标记已经访问if (num[x][y]){//如果当前格子有值,取maxans = max(ans, num[x][y]);continue;}for (int i = 1; i <= 8; i++){
//这里的i代表移动方向,同时也代表了移动方向后所要减少的体力值if (i > hp) break;//如果消耗值>当前体力值,就不用进行移动了int xx = x + D[i][0], yy = y + D[i][1];if (xx<1 || yy<1 || xx>n || yy>m) continue;q.push({xx, yy, hp - i});//更新下一个格子的值}}cout << ans << endl;
}signed main(){solve();
}
更多推荐
I:寻宝任务
发布评论