14111: 【原4111】labyrinth

题目描述

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

Description

dhh是个狂热的密室逃脱爱好者。xyy约他去游乐园时，他都拒绝；他只爱密室逃脱。

现在dhh来到了一个迷宫密室逃脱。这个由$N$行$M$列个房间组成，每个房间有四扇门可以通向其上下左右四个房间，但是如果某个房间的门通向了迷宫外，这扇门就会被堵死。同时有些设有鬼屋，由于dhh怕鬼，所以他不想经过这些房间。

现在告诉你dhh的起始位置以及迷宫密室的出口，dhh想知道他最少需要经过几扇门才能到达出口。

Input Format

第一行两个正整数$N,M$，表示迷宫的规格为$N$行$M$列。

接下来一个$N$行$M$列的矩阵，每个元素表示迷宫每个房间的状态，矩阵由$4$种字符构成。

'.'表示这个房间可以正常经过。
'#'表示此房间设有鬼屋。
'@'表示dhh的起始房间。
'$'表示迷宫密室的出口所在的房间。

Output Format

输出一行一个整数，表示答案。

若dhh怎么都无法到达出口，请输出$-1$。

Sample Input

3 4
@...
.#..
$...

Sample Output

Data Range

对于$30\%$的数据，$N,M \le 10$。

对于另外$20\%$的数据，没有'#'。

对于$100 \%$的数据，$N,M \le 1000$。'@''$'保证出且仅出现一次。数据完全随机制造。

FineArtz's solution

/* labyrinth */
#include <iostream>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct Node{
    int x = 0, y = 0, step = 0;
};

char ch;
char a[1005][1005];
bool b[1005][1005] = {false};
int n, m;
int sx, sy;
Node q[1000005];
int front = 0, rear = 0;

void bfs(){
    Node s;
    s.x = sx;
    s.y = sy;
    q[rear++] = s;
    b[sx][sy] = true;
    while (front != rear){
        Node now = q[front];
        ++front;
        for (int k = 0; k < 4; ++k){
            int nx = now.x + dx[k];
            int ny = now.y + dy[k];
            if (nx > 0 && nx <= n && ny > 0 && ny <= m && !b[nx][ny]){
                Node next;
                next.x = nx;
                next.y = ny;
                next.step = now.step + 1;
                if (a[nx][ny] == '$'){
                    cout << next.step << endl;
                    return;
                }
                b[nx][ny] = true;
                q[rear++] = next;
            }
        }
    }
    cout << "-1" << endl;
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            cin >> a[i][j];
            if (a[i][j] == '@'){
                sx = i;
                sy = j;
            }
            else if (a[i][j] == '#'){
                b[i][j] = true;
            }
        }
    }
    bfs();
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
char map[1005][1005];
int minx[1005][1005],qx[1000011],qy[1000011];
int sx,sy,head,tail,m,n,now,xnow,ynow,ex,ey;
void update(int value,int x,int y)
{
    if (map[x][y]=='#') return;
    if ((map[x][y]=='$'||map[x][y]=='.')&&(minx[x][y]==0)) {
        minx[x][y] = value;
        qx[tail] = x;
        qy[tail] = y;
        tail++;
    }
}
int main() {
    scanf("%d%d",&m,&n);
    for (int i=0;i<m;++i)
    {
        scanf("%s",map[i]);
        for (int j=0;j<n;++j) {
            if (map[i][j] == '@') {
                sx = i;
                sy = j;
            }
            if (map[i][j] == '$'){
                ex = i;
                ey = j;
            }
        }
    }
    qx[0]=sx;
    qy[0]=sy;
    head=0;
    tail=1;
    while (head<tail)
    {
        now=minx[qx[head]][qy[head]];
        xnow=qx[head];
        ynow=qy[head];
        if (xnow>=1) update(now+1,xnow-1,ynow);
        if (ynow>=1) update(now+1,xnow,ynow-1);
        if (xnow<m-1) update(now+1,xnow+1,ynow);
        if (ynow<n-1) update(now+1,xnow,ynow+1);
        head++;
        if (minx[ex][ey]!=0) break;

    }
    if (!minx[ex][ey]) printf("%d",-1);
    else printf("%d",minx[ex][ey]);
    return 0;
}