14947 상자 배달

bfs 문제다.

1*1짜리로 서 있을때는 그 자리를 위치로 잡고

1*3 or 3*1로 누워있을 땐 중간을 위치로 잡는다

그리고 [x][y][형태]로 배열을 잡은 뒤에 bfs를 돌리면 된다.

유의할 점은 누워있을 때 똑바로 서는 것 말고도 옆으로 구르는 것도 잘 계산해 줘야 한다는 점과

해당 자리에 위치할 수 있는지를 확인 할 때 3도 땅으로 체크해야 한다는 것이다.

#include <stdio.h>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
 
/*
1 = 1*1
2 = 1*3
3 = 3*1
*/
 
struct p {
    int x, y, w;
    p(int x, int y, int w) : x(x), y(y), w(w) {}
};
 
int n, m, a[501][501], tx, ty, dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
short d[501][501][4], f;
queue<p> q;
 
bool check(int x, int y, int i) {
    int cnt = 0;
    for (int j = -1; j < 2; j += 2) {
        int nnx = x + dx[i] * j, nny = y + dy[i] * j;
        if (nnx >= n || nny >= m || nnx < 0 || nny < 0) return 0;
        if (a[nnx][nny] == 1 || a[nnx][nny] == 3) cnt++;
    }
    if (cnt != 2 && !a[x][y]) return 0;
    return 1;
}
void check2(int x, int y, int i) {
    for (int j = -1; j < 2; j++) if (a[x + dx[i] * j][y + dy[i] * j] == 3)
        f = 1;
}
 
int main() {
    memset(d, -1, sizeof(d));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        scanf("%1d", &a[i][j]);
        if (a[i][j] == 2) {
            d[i][j][1] = 0;
            q.push({ i,j,1 });
        }
        else if (a[i][j] == 3) tx = i, ty = j;
    }
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, w = q.front().w;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i] * 2, ny = y + dy[i] * 2, nw = i / 2 ? 3 : 2;
            if (w == 1) {
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || d[nx][ny][nw] != -1 || !check(nx, ny, i)) continue;
                check2(nx, ny, i);
                d[nx][ny][nw] = d[x][y][w] + 1;
                q.push({ nx,ny,nw });
            }
            else {
                if ((i / 2 && w == 3) || (!(i / 2) && w == 2)) {
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || a[nx][ny] == 0 || d[nx][ny][1] != -1) continue;
                    if (a[nx][ny] == 3) f = 1;
                    d[nx][ny][1] = d[x][y][w] + 1;
                    q.push({ nx,ny,1 });
                }
                else {
                    nx -= dx[i], ny -= dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || d[nx][ny][w] != -1 || !check(nx, ny, (i + 2) % 4)) continue;
                    check2(nx, ny, (i + 2) % 4);
                    d[nx][ny][w] = d[x][y][w] + 1;
                    q.push({ nx,ny,w });
                }
            }
            if (f) {
                printf("%hd", d[x][y][w] + 1);
                return 0;
            }
        }
    }
    printf("%d", -2);
    return 0;
}