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到达终点的最小步数,输入数据保证终点是一定可达的。

Input Format

第一行:四个用空格分开的整数:M,N,M1和M2, 1 ≤ M, N ≤ 30,1 ≤ M1 ≤ 30,1 ≤ M2 ≤ 30,M1 ≠ M2

第二行到M + 1行:第i + 1行有N个用空格分开的整数,描述了池塘第i行的状态:0 为水,1 为岩石,2 为沼泽,3 为起点,4 为终点。

Output Format

第一行:从起点到终点的最少步数

Sample Input

Sample Output

数据说明

先跳到 1 行 3 列的岩石上,再跳到终点,需要 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;
    int head, tail;

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

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

    void pop() { ++head; }

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