# 14065: 【原4065】泷的旅途

### 题目描述

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

## Description

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

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