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;
}