[Jungol] 정올 1661 미로 탈출 로봇

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=934&sca=50

 Input 

8 7

1 2 7 5

11111111

00000111

10110011

10111001

10111101

10000001

11111111

 

 Output 

9

※ 주어지는 Input Data가 열의 크기, 행의 크기 순으로 주어지므로 2차원 배열을 구성할 때 주의.

※ map[][] 크기는 100 × 100이므로 Queue에 최대 담기는 개수는 10000개 입니다.

※ scanf("%1d", &map[i][j]);를 통해 공백없이 연속해서 받는 숫자를 한 자리씩 처리할 수 있습니다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define INF 2e9
struct ROBOT {
    int x, y, time;
}que[100 * 100];
int X, Y, sx, sy, ex, ey;
int map[101][101], visited[101][101];;
int dr[] = { 0, 0, 1, -1 };
int dc[] = { 1, -1, 0, 0 };
int fr, re;
 
void input() {
    scanf("%d %d", &Y, &X);
    scanf("%d %d %d %d", &sy, &sx, &ey, &ex);
 
    for (int i = 1; i <= X; ++i) {
        for (int j = 1; j <= Y; ++j) {
            scanf("%1d", &map[i][j]);
        }
    }
}
 
void push(int x, int y, int time) {
    // 범위를 벗어나는 경우
    if (x < 1 || y < 1 || x > X || y > Y) {
        return;
    }
 
    // 벽(장애물)인 경우
    if (map[x][y] == 1) {
        return;
    }
 
    // 이전에 방문한 것보다 늦게 도착한 경우
    if (visited[x][y]) return;
 
    visited[x][y] = 1;
    que[re++] = { x, y, time };
}
 
int BFS() {
    ROBOT cur;
    push(sx, sy, 0);
    while (fr < re) {
        cur = que[fr++];
        // 두 고슴도치가 모두 집에 도착한 경우
        if (cur.x == ex && cur.y == ey)
            return cur.time;
 
        for (int i = 0; i < 4; ++i)
            push(cur.x + dr[i], cur.y + dc[i], cur.time + 1);
    }
    return -1;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    printf("%d\n", BFS());
}