# 13008: 【原3008】Maze

### 题目描述

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

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