[백준 16973번] 직사각형 탈출

문제 링크: https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

<문제 풀이> BFS

직사각형의 좌측 상단의 좌표로 BFS를 진행하면 되는데 이때 격자판을 넘어가는지, 벽을 만나는지를 체크할 때 직사각형의 전체를 확인할 필요가 없다 -> O(HW)

 다음 방향으로 이동할 때 이동한 면적만 확인하면 된다. ->O(H) or O(W)

<C++ 소스 코드>

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
 
#define X first
#define Y second
 
enum{LEFT, RIGHT, UP, DOWN};
int N, M;
int board[1001][1001];
int dist[1001][1001];
int H, W, Sr, Sc, Fr, Fc;
const int dx[4] = { 0, 0, -1, 1 }; //LEFT, RIGHT, UP, DOWN
const int dy[4] = { -1, 1, 0, 0 };
 
bool moveable(int r, int c, int dir) {
    if (dir == LEFT) {
        if (c - 1 < 1) return false;
        if (dist[r][c - 1] != -1) return false;
        for (int i = 0; i < H; i++) {
            if (board[r + i][c - 1] == 1) return false;
        }
    }
    else if (dir == RIGHT) {
        if (c + W > M) return false;
        if (dist[r][c + 1] != -1) return false;
        for (int i = 0; i < H; i++) {
            if (board[r + i][c + W] == 1) return false;
        }
    }
    else if (dir == UP) {
        if (r - 1 < 1) return false;
        if (dist[r - 1][c] != -1) return false;
        for (int i = 0; i < W; i++) {
            if (board[r - 1][c + i] == 1) return false;
        }
    }
    else if (dir == DOWN) {
        if (r + H > N) return false;
        if (dist[r + 1][c] != -1) return false;
        for (int i = 0; i < W; i++) {
            if (board[r + H][c + i] == 1) return false;
        }
    }
    return true;
}
int bfs() {
    queue<pair<int, int> > Q;
    Q.push({ Sr, Sc });
    dist[Sr][Sc] = 0;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        if (cur.X == Fr && cur.Y == Fc) return dist[cur.X][cur.Y];
        for (int dir = 0; dir < 4; dir++) {
            if (moveable(cur.X, cur.Y, dir)) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                Q.push({nx, ny });
                dist[nx][ny] = dist[cur.X][cur.Y] + 1;
            }
        }
    }
    return -1;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> board[i][j];
            dist[i][j] = -1;
        }
    }
    cin >>H>>W >>Sr >> Sc >> Fr >> Fc;
    cout << bfs();
    return 0;
}