14111: 【原4111】labyrinth

题目描述

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

Description

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

Input Format

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

Sample Input

``````3 4
@...
.#..
\$...
``````

Sample Output

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

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];
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;
tail=1;
{