[16973] 직사각형 탈출

https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

<문제>

"[2194] 유닛 이동시키기"보다 조금 더 강화된 문제이다.

해당 문제는 먼저 큐에 넣고 이후에 검사하는 방식으로 간단하게만 구현했지만, 이 문제는 입력이 커졌다.

 

왼쪽으로 이동할때를 생각해보면, 직사각형의 가장 왼쪽면만 검사하면

해당 정점이 정말로 가능한 정점인지를 파악할 수 있다. 어처피 입력으로 들어오는 초기상태의 직사각형은

맵 안에, 그것도 장애물이 없는곳에 위치해있으니 초기정점에 대한 정점의 조건은 전혀 생각하지 않아도 된다.

그렇기에 초기상태의 조건이 충족되었음을 보장하고, 정점의 조건을 이동할때마다 검사한다면 방향에 따른

{첫행, 마지막 행, 첫열, 마지막 열}중 하나만 검사하면 된다. 이를 수행하는것을 코드의 canMove()로 구현했다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b, ey, ex, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
bool check[1001][1001], visited[1001][1001];
typedef struct {
    int y, x, cnt;
} state;
bool canMove(int key, int y, int x, int yy, int xx) {
    if (key == 0)
        for (int i = y; i <= yy; i++)
            if (check[i][xx]) return false;
    if (key == 1)
        for (int i = x; i <= xx; i++)
            if (check[yy][i]) return false;
    if (key == 2)
        for (int i = y; i <= yy; i++)
            if (check[i][x]) return false;
    if (key == 3)
        for (int i = x; i <= xx; i++)
            if (check[y][i]) return false;
    return true;
}
int bfs(int sy, int sx) {
    queue<state> q;
    q.push({sy, sx, 0});
    visited[sy][sx] = true;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.y == ey && cur.x == ex) return cur.cnt;
 
        for (int i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            int yy = y + a - 1;
            int xx = x + b - 1;
            if (y < 0 || x < 0 || y >= n || x >= m || yy < 0 || xx < 0 ||
                yy >= n || xx >= m)
                continue;
            if (visited[y][x] == 0 && canMove(i, y, x, yy, xx)) {
                visited[y][x] = true;
                q.push({y, x, cur.cnt + 1});
            }
        }
    }
    return -1;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int sy, sx;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> check[i][j];
    cin >> a >> b >> sy >> sx >> ey >> ex;
    sy--;
    sx--;
    ey--;
    ex--;
    cout << bfs(sy, sx);
    return 0;
}