[2194] 유닛 이동시키기

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

2194번: 유닛 이동시키기

<문제>

구현의 편의상 전부 4방향을 넣어 준 뒤, 큐에서 노드를 가져온 직후 ( [cury, cury+a), [curx, curx+b) )를 전부 순회하며

장애물이 있는 칸이 포함되었거나, 맵을 빠져나간 곳이 있는지를 체크했다.

하나라도 있으면 애초에 정점의 조건을 만족하지 않으므로 바로 continue해주고,

큐에 push하는 부분에서는, 어처피 정점의 조건은 push하고 pop한 뒤에 검사하므로

이를 중복으로 검사하지 않고 정점의 중복방문만 체크해주고 그냥 push해주었다.

 

1개짜리 칸이 아닌, 장애물이 있는 n*m의 맵에서 a*b의 블럭을 움직이는 문제의 가장 어려운 부분은

다소 비효율적이지만 구현의 편의상 위처럼 진행해주었다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, a, b, k, ey, ex, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
bool check[503][503], visited[503][503];
typedef struct {
    int y, x, cnt;
} state;
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();
        bool flag = false;
        for (int i = cur.y; i < cur.y + a; i++) {
            for (int j = cur.x; j < cur.x + b; j++) {
                if (i < 0 || j < 0 || i >= n || j >= m) {
                    flag = true;
                    goto skip;
                }
                if (check[i][j]) {
                    flag = true;
                    goto skip;
                }
            }
        }
    skip:
        if (flag) continue;
        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];
            if (visited[y][x] == false) {
                visited[y][x] = true;
                q.push({y, x, cur.cnt + 1});
            }
        }
    }
    return -1;
}
int main(void) {
    cin >> n >> m >> a >> b >> k;
    int i, j;
    for (i = 0; i < k; i++) {
        int y, x;
        cin >> y >> x;
        check[y - 1][x - 1] = true;
    }
    int sy, sx;
    cin >> sy >> sx;
    cin >> ey >> ex;
    sy--;
    sx--;
    ey--;
    ex--;
    cout << bfs(sy, sx);
    return 0;
}