Skip to content

13008: 【原3008】Maze

题目

题目描述

author: snow_sword 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3008

Description

这一年,我们交大有了一位新的同学——二哥。二哥初来乍到,对交大的地形不是很熟悉,这对他去上课造成了很大的麻烦。不过还好,现在二哥手中有一份交大的地图来帮助他去上课。交大的地形十分复杂,有四种地形: (二哥只能上下左右移动)

通路 ”.”:可以上下左右移动; (英文句号 . )

桥 ”|”:只能上下移动; (C++中的或 | )

桥 ”-“:只能左右移动; (减号)

墙 “*“: 不能通行。 (乘号)

现在二哥在地图上的(x1, y1)位置,上课地点在(x2, y2)处,请你帮二哥找出一条路径去上课。由于时间紧迫,二哥希望知道他所在的位置离上课地点有多远。你只需输出小明当前位置离上课地点的最短距离。如果无法到达上课地点,请输出-1。输入数据保证起点和终点是通路 “.“

Input Format

第1行: n, m 给出交大地图的长和宽,用空格分隔

第2行: x1, y1, x2, y2 给出小明的位置(x1, y1) 和目的地(x2, y2),每两个数中间用空格分隔。x表示行,y表示列。

第3到n+2行: 每行m个字符,描述了交大的地形。每个字符之间没有空格。

Output Format

一行,输出最短距离。

数据范围

对于30%的数据,n,m<=20,且没有桥”|””-”只有通路和墙”.””*”

对于60%的数据,n,m<=100, 且没有桥”|””-”只有通路和墙”.””*”

对于100%的数据,n,m<=100.

Sample Input

4 5
2 2 3 4
.....
..**.
.**..
.....

Sample Output

7

Sample Input

4 5
1 3 2 5
...-|
.*|*.
.*|-.
...-.

Sample Output

7

Sample Input

3 3
1 3 3 1
.*.
*.*
.*.

Sample Output

-1

Sample Input

2 2
1 1 2 2
.*
|.

Sample Output

-1

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e2 + 100;

int n, m, x1, y1, x2, y2, sjtu[maxN][maxN] = {0}, ans = 1e8;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
bool visited[maxN][maxN] = {0};

struct Node {
    int x, y, sum;

    Node(int a = 0, int b = 0, int c = 0) : x(a), y(b), sum(c) {}
};

template <class elemType>
class seqQueue {
   private:
    elemType *data;
    int maxSize;
    int front, rear;
    void doubleSpace();

   public:
    seqQueue(int size = 1e5);
    ~seqQueue();
    bool isEmpty() const;
    void enQueue(const elemType &);
    elemType deQueue();
    elemType getHead() const;
    int length() const;
};

template <class elemType>
void seqQueue<elemType>::doubleSpace() {
    elemType *tmp = data;
    data = new elemType[maxSize * 2];

    for (int i = 1; i <= maxSize; i++) {
        data[i] = tmp[(front + i) % maxSize];
    }

    front = 0;
    rear = maxSize;
    maxSize *= 2;
    delete[] tmp;
}

template <class elemType>
seqQueue<elemType>::seqQueue(int size) : maxSize(size), front(0), rear(0) {
    data = new elemType[size];
}

template <class elemType>
seqQueue<elemType>::~seqQueue() {
    delete[] data;
}

template <class elemType>
bool seqQueue<elemType>::isEmpty() const {
    return front == rear;
}

template <class elemType>
void seqQueue<elemType>::enQueue(const elemType &x) {
    /*if ((rear + 1) % maxSize == front) {
        doubleSpace();
    }*/
    rear = (rear + 1) % maxSize;
    data[rear] = x;
}

template <class elemType>
elemType seqQueue<elemType>::deQueue() {
    front = (front + 1) % maxSize;
    return data[front];
}

template <class elemType>
elemType seqQueue<elemType>::getHead() const {
    return data[(front + 1) % maxSize];
}

template <class elemType>
int seqQueue<elemType>::length() const {
    return ((rear + maxSize - front) % maxSize);
}

seqQueue<Node> que;

void BFS(int, int, int, int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> x1 >> y1 >> x2 >> y2;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char temp;
            cin >> temp;
            switch (temp) {
                case '.':
                    sjtu[i][j] = 1;
                    break;
                case '|':
                    sjtu[i][j] = 2;
                    break;
                case '-':
                    sjtu[i][j] = 3;
                    break;
                case '*':
                    sjtu[i][j] = 0;
                    break;
            }
        }
    }

    BFS(x1, y1, x2, y2, 0);

    if (ans == (int)1e8) {
        ans = -1;
    }

    cout << ans;

    return 0;
}

void BFS(int x1, int y1, int x2, int y2, int sum) {
    Node start(x1, y1, 0);
    que.enQueue(start);

    visited[x1][y1] = 1;

    while (!que.isEmpty()) {
        Node now = que.deQueue();

        int temp = sjtu[now.x][now.y];

        if (temp == 1) {
            for (int i = 0; i < 2; i++) {
                if ((sjtu[now.x + dx[i]][now.y] == 1 ||
                     sjtu[now.x + dx[i]][now.y] == 2) &&
                    !visited[now.x + dx[i]][now.y]) {
                    Node next(now.x + dx[i], now.y, now.sum + 1);
                    que.enQueue(next);
                    visited[next.x][next.y] = 1;
                    if (next.x == x2 && next.y == y2) {
                        ans = next.sum;
                        return;
                    }
                }
            }

            for (int i = 2; i < 4; i++) {
                if ((sjtu[now.x][now.y + dy[i]] == 1 ||
                     sjtu[now.x][now.y + dy[i]] == 3) &&
                    !visited[now.x][now.y + dy[i]]) {
                    Node next(now.x, now.y + dy[i], now.sum + 1);
                    que.enQueue(next);
                    visited[next.x][next.y] = 1;
                    if (next.x == x2 && next.y == y2) {
                        ans = next.sum;
                        return;
                    }
                }
            }
        } else if (temp == 2) {
            for (int i = 0; i < 2; i++) {
                if ((sjtu[now.x + dx[i]][now.y] == 1 ||
                     sjtu[now.x + dx[i]][now.y] == 2) &&
                    !visited[now.x + dx[i]][now.y]) {
                    Node next(now.x + dx[i], now.y, now.sum + 1);
                    que.enQueue(next);
                    visited[next.x][next.y] = 1;
                    if (next.x == x2 && next.y == y2) {
                        ans = next.sum;
                        return;
                    }
                }
            }
        } else if (temp == 3) {
            for (int i = 2; i < 4; i++) {
                if ((sjtu[now.x][now.y + dy[i]] == 1 ||
                     sjtu[now.x][now.y + dy[i]] == 3) &&
                    !visited[now.x][now.y + dy[i]]) {
                    Node next(now.x, now.y + dy[i], now.sum + 1);
                    que.enQueue(next);
                    visited[next.x][next.y] = 1;
                    if (next.x == x2 && next.y == y2) {
                        ans = next.sum;
                        return;
                    }
                }
            }
        }
    }
}

yyong119's solution

#include <iostream>
#include <queue>
#define MAX_N 105
using namespace std;
// up, down, left, right
const int ac[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct Node {
    int x, y, cnt;
    Node(int p = 0, int q = 0, int k = 0): x(p), y(q), cnt(k) {}
};
int n, m, sx, sy, ex, ey;
int step_cnt[MAX_N][MAX_N];
char map[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];
queue<Node> q;
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> sx >> sy >> ex >> ey;
    for (register int i = 1; i <= n; ++i)
        for (register int j = 1; j <= m; ++j)
            cin >> map[i][j];
    if (map[ex][ey] == '*') {
        cout << -1;
        return 0;
    }
    // push the start node into queue
    q.push(Node(sx, sy, 0)); vis[sx][sy] = true;
    // bfs
    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        if (cur.x == ex && cur.y == ey) {
            cout << cur.cnt;
            return 0;
        }
        if (map[cur.x][cur.y] == '.')
            for (register int i = 0; i < 4; ++i) {
                int x = cur.x + ac[i][0], y = cur.y + ac[i][1];
                if (x && x <= n && y && y <= m && !vis[x][y] && 
                (map[x][y] == '.' || map[x][y] == '-' && cur.x == x || map[x][y] == '|' && cur.y == y)) {
                    vis[x][y] = true;
                    q.push(Node(x, y, cur.cnt + 1));
                }
            }
        else if (map[cur.x][cur.y] == '-') {
            // go right
            if (cur.y < m && !vis[cur.x][cur.y + 1] && (map[cur.x][cur.y + 1] == '-' || map[cur.x][cur.y + 1] == '.')) {
                vis[cur.x][cur.y + 1] = true;
                q.push(Node(cur.x, cur.y + 1, cur.cnt + 1));
            }
            // go left
            if (cur.y > 1 && !vis[cur.x][cur.y - 1] && (map[cur.x][cur.y - 1] == '-' || map[cur.x][cur.y - 1] == '.')) {
                vis[cur.x][cur.y - 1] = true;
                q.push(Node(cur.x, cur.y - 1, cur.cnt + 1));
            }
        }
        else if (map[cur.x][cur.y] == '|') {
            // go bottom
            if (cur.x < n && !vis[cur.x + 1][cur.y] && (map[cur.x + 1][cur.y] == '|' || map[cur.x + 1][cur.y] == '.')) {
                vis[cur.x + 1][cur.y] = true;
                q.push(Node(cur.x + 1, cur.y, cur.cnt + 1));
            }
            // go up
            if (cur.x > 1 && !vis[cur.x - 1][cur.y] && (map[cur.x - 1][cur.y] == '|' || map[cur.x - 1][cur.y] == '.')) {
                vis[cur.x - 1][cur.y] = true;
                q.push(Node(cur.x - 1, cur.y, cur.cnt + 1));
            }
        }
    }
    cout << -1;
    return 0;
}