# 11281: 【原1281】蹦蹦跳跳

### 题目描述

author: Chen Xutong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1281

## Description

cxt出发了，他要去找时光机，可是距离好远，因为他生存在远古时期，木有轮船，飞机，大炮什么的。于是只能跳回去 = =。地图是一个矩形，可以划分成M × N个方格。一些格子是岩石,还有一些沼泽，其余的只是美丽、纯净、湛蓝的水。因为cxt不会游泳 = =。cxt每次站在一块岩石上,想跳到另一块岩石上,他只能从一块岩石跳到另一块岩石上,既不能跳到水里,也不能跳到沼泽里。因为cxt有惊人的弹跳能力，他的跳法很像象棋中的马步:每次跳跃可以横移M1格,纵移M2格,或纵移M1格,横移M2格,最多有八个方向可供移动选择。请计算cxt到达终点的最小步数,输入数据保证终点是一定可达的。

## Sample Input

``````4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0
``````

## Sample Output

``````2
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/17.
//
//
// Created by BugenZhao on 2019/4/5.
//

#ifndef SBL_BQUEUE_H
#define SBL_BQUEUE_H

#include <iostream>

template<typename Item>
class BQueue {
class Node {
public:
Item item;
Node *next;

explicit Node(const Item &item, Node *next = nullptr) : item(item), next(next) {}

explicit Node(Node *next = nullptr) : next(next) {}

virtual ~Node() = default;
};

int N;
Node *first;
Node *last;

public:
BQueue() {
N = 0;
first = last = nullptr;
}

bool isEmpty() const {
return N == 0;
}

int size() const {
return N;
}

void enqueue(Item item) {
if (N == 0) {
first = new Node{item};
last = first;
} else {
Node *tmp = last;
last = new Node{item};
tmp->next = last;
}
++N;
}

Item dequeue() {
Item item = first->item;
Node *tmp = first;
first = first->next;
if (N == 1) last = nullptr;
delete tmp;
--N;
return item;
}

Item getFirst() const {
return first->item;
}

Item getLast() const {
return last->item;
}

void clear() {
Node *tmp;
while (first != nullptr) {
tmp = first;
first = first->next;
delete tmp;
}
N = 0;
first = last = nullptr;
}

virtual ~BQueue() {
Node *tmp;
while (first != nullptr) {
tmp = first;
first = first->next;
delete tmp;
}
}

private:
class Iterator {
Node *it;
Node *first;
Node *last;
public:

Iterator(Node *first, Node *last) :
it(first), first(first), last(last) {}

bool hasNext() const {
return it != nullptr;
}

Item &next() {
Node *p = it;
it = it->next;
return p->item;
}

const Item &next() const {
Node *p = it;
it = it->next;
return p->item;
}
};

public:
Iterator iterator() const {
return Iterator(first, last);
}
};

#endif //SBL_BQUEUE_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

class Point {
public:
int x, y;

Point(int x = 0, int y = 0) :
x(x), y(y) {}
};

int height[30][30];
Point from[30][30];
bool flag[30][30];
int X0, Y0, X, Y;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, m1, m2;
cin >> m >> n >> m1 >> m2;
int dx[] = {m1, m1, m2, m2, -m1, -m1, -m2, -m2};
int dy[] = {m2, -m2, m1, -m1, m2, -m2, m1, -m1};

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> height[i][j];
if (height[i][j] == 3) X0 = i, Y0 = j;
else if (height[i][j] == 4) X = i, Y = j;
}
}

BQueue<Point> q;
q.enqueue(Point(X0, Y0));
from[X0][Y0] = {-1, -1};
flag[X0][Y0] = true;

while (!q.isEmpty()) {
Point point = q.dequeue();
for (int i = 0; i < 8; ++i) {
int xx = point.x + dx[i];
int yy = point.y + dy[i];
if (xx < 0 || xx >= m || yy < 0 || yy >= n || flag[xx][yy]) continue;
if (height[xx][yy] == 0 || height[xx][yy] == 2) continue;
if (height[xx][yy] == 4) {
int ans = 1;
int x = point.x, y = point.y;
while (true) {
if (x == X0 && y == Y0) break;
++ans;
Point tmp = from[x][y];
x = tmp.x, y = tmp.y;
}
cout << ans << endl;
return 0;
}
if (height[xx][yy] == 1) {
flag[xx][yy] = true;
q.enqueue(Point(xx, yy));
from[xx][yy] = Point(point.x, point.y);
}
}
}
}
``````

## ligongzzz's solution

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

template <class T>
class my_queue {
public:
T queue_[50000];
int start = 0, end = 0;
int mod = 50000;
void clear() {
start = 0;
end = 0;
memset(queue_, 0, sizeof(queue_));
}
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;
}
};

class position {
public:
int distance = 0;
int pos_x = 0, pos_y = 0;

position() = default;
position(int dis, int x, int y) :distance(dis), pos_x(x), pos_y(y) {}
};

int map_data[49][49] = { 0 };

bool visited[49][49] = { 0 };
int dx[8], dy[8];
int n, m;

my_queue<position> queue_data;
int bfs(int start_x, int start_y, int end_x, int end_y) {
queue_data.clear();
memset(visited, 0, sizeof(visited));
position start_point(0, start_x, start_y);
queue_data.push(start_point);
visited[start_x][start_y] = true;

while (!queue_data.empty()) {
auto temp = queue_data.front();
queue_data.pop();

if (temp.pos_x == end_x && temp.pos_y == end_y) {
return temp.distance;
}

for (int i = 0; i < 8; ++i) {
if (temp.pos_x + dx[i] >= 0 && temp.pos_x + dx[i] < m &&
temp.pos_y + dy[i] >= 0 && temp.pos_y + dy[i] < n &&
!visited[temp.pos_x + dx[i]][temp.pos_y + dy[i]]
&& map_data[temp.pos_x + dx[i]][temp.pos_y + dy[i]] != 0
&& map_data[temp.pos_x + dx[i]][temp.pos_y + dy[i]] != 2) {
position next_point(temp.distance + 1, temp.pos_x + dx[i], temp.pos_y + dy[i]);
queue_data.push(next_point);
visited[next_point.pos_x][next_point.pos_y] = true;
}
}
}
return -1;
}

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

dx[0] = m1, dy[0] = m2;
dx[1] = m1, dy[1] = -m2;
dx[2] = -m1, dy[2] = m2;
dx[3] = -m1, dy[3] = -m2;
dx[4] = m2, dy[4] = m1;
dx[5] = m2, dy[5] = -m1;
dx[6] = -m2, dy[6] = m1;
dx[7] = -m2, dy[7] = -m1;

int start_x, start_y, end_x, end_y;

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
scanf("%d", &map_data[i][j]);
if (map_data[i][j] == 3) {
start_x = i;
start_y = j;
}
else if (map_data[i][j] == 4) {
end_x = i;
end_y = j;
}
}
}

cout << bfs(start_x, start_y, end_x, end_y);

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <queue>

using namespace std;

bool visited[30][30] = {0};
int MAP[30][30];

int M, N, M1, M2;
int sx, sy, ex, ey;

inline bool is_ok(int x, int y) {
if (x >= 0 && y >= 0 && x < M && y < N) {
if (MAP[x][y] == 1 || MAP[x][y] == 3 || MAP[x][y] == 4) {
return true;
}
}
return false;
}

int ans = INT_MAX;

int dir[8][2] = {0};

struct Record {
int x, y, step;

Record(int x, int y, int step) : x(x), y(y), step(step) {};

Record() {};
};

template<typename T>
struct Queue {
T *x;

Queue(int cap) : head(0), tail(0) { x = new T[cap]; }

void push(const T &d) { x[tail++] = d; }

T &front() { return x[head]; }

T &rear() { return x[tail - 1]; }

bool empty() { return head == tail; }
};

int bfs() {
Queue<Record> q(10000);
Record c(sx, sy, 0), p;
q.push(c);
while (!q.empty()) {
p = q.front();
q.pop();
if (p.x == ex && p.y == ey) {
return p.step;
}
for (int d = 0; d < 8; d++) {
int _x = p.x + dir[d][0];
int _y = p.y + dir[d][1];
if (is_ok(_x, _y)) {
if (!visited[_x][_y]) {
visited[_x][_y] = true;
q.push(Record(_x, _y, p.step + 1));
}
}
}
}
}

int main() {
cin >> M >> N >> M1 >> M2;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> MAP[i][j];
if (MAP[i][j] == 3) {
sx = i;
sy = j;
}
if (MAP[i][j] == 4) {
ex = i;
ey = j;
}
}
}
dir[0][0] = M1;
dir[0][1] = M2;
dir[1][0] = M1;
dir[1][1] = -M2;
dir[2][0] = -M1;
dir[2][1] = M2;
dir[3][0] = -M1;
dir[3][1] = -M2;
dir[4][1] = M1;
dir[4][0] = M2;
dir[5][1] = M1;
dir[5][0] = -M2;
dir[6][1] = -M1;
dir[6][0] = M2;
dir[7][1] = -M1;
dir[7][0] = -M2;
cout << bfs() << endl;
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N = 35;
struct node {
node(int a, int b, int p) {
x = a; y = b; step = p;
};
int x, y, step;
};

int main() {

int n, m, N, M;
cin >> n >> m >> N >> M;
const int movement[8][2] = { {N, M}, {M, N}, {-N, M}, {-M, N}, {-N, -M}, {-M, -N}, {N, -M}, {M, -N} };
int a[MAX_N][MAX_N]; memset(a, 0, sizeof(a));
bool visited[MAX_N][MAX_N]; memset(visited, false, sizeof(visited));
queue<node> que;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
if (a[i][j] != 1 && a[i][j] != 4) visited[i][j] = true;
if (a[i][j] == 3) que.push(node(i, j, 0));
}
bool found = false;
int ans;
while (!que.empty()) {
node now = que.front();
for (int i = 0; i < 8; ++i) {
int nextx = now.x + movement[i][0], nexty = now.y + movement[i][1];
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if (!visited[nextx][nexty]) {
if (a[nextx][nexty] == 4) {
found = true;
ans = now.step + 1;
break;
}
que.push(node(nextx, nexty, now.step + 1));
visited[nextx][nexty] = true;
}
}
if (found) break;
que.pop();
}
cout << ans << endl;
return 0;
}
``````