통나무 옮기기

#include<iostream>
#include<queue>
#include<utility>
 
using namespace std;
 
struct P{
    int x, y, rot;
    P(int x, int y, int rot) {
        this->x = x;
        this->y = y;
        this->rot = rot;
    }
};
int n;
string map[51];
bool d[51][51][2];
int ex = 0, ey = 0;
int dist[51][51][2];
int ans = 987654321;
bool findd = false;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void bfs(int x, int y, int rot) {
    queue<P> q;//rot = 1 1 rot = 0 ㅡ
    q.push(P(x,y,rot));
    d[x][y][rot] = true;
    while (!q.empty()) {
        x = q.front().x; y = q.front().y; rot = q.front().rot;
        q.pop();
        for (int i = 0; i < 5; i++) {
            if (i < 4) {
                int nx = x + dx[i]; int ny = y + dy[i];
                    if (rot == 0) {
                        if (nx >= 0 && nx < n && ny > 0 && ny < n - 1) {
                            if ((map[nx][ny] =='0'||map[nx][ny]=='B'||map[nx][ny]=='E')&& ny> 0 && ny < n-1&&
(map[nx][ny + 1] == '0' || map[nx][ny + 1] == 'B' ||map[nx][ny+1]=='E') &&
                                (map[nx][ny - 1] == '0' || map[nx][ny - 1] == 'B'||map[nx][ny-1]=='E')&&d[nx][ny][rot]==false) {
                                d[nx][ny][rot] = true;
                                dist[nx][ny][rot] = dist[x][y][rot] + 1;
                                if (map[nx][ny] == 'E' && map[nx][ny - 1] == 'E' && map[nx][ny + 1] == 'E') {
                                    if (ans > dist[nx][ny][rot]) {
                                        ans = dist[nx][ny][rot]; findd = true;
                                    }
                                }
                                q.push(P(nx, ny, rot));
                            }
                        }
                    }
                    else if(rot == 1) {
                        if (nx > 0 && nx < n - 1 && ny >= 0 && ny < n) {
                            if ((map[nx][ny] == '0' || map[nx][ny] == 'B' || map[nx][ny] == 'E') && nx > 0 
&& nx < n-1 &&(map[nx + 1][ny] == '0' || map[nx + 1][ny] == 'B'||map[nx+1][ny]=='E') &&
                                (map[nx - 1][ny] == '0' || map[nx - 1][ny] == 'B'||map[nx-1][ny]=='E') &&d[nx][ny][rot]==false) {
                                d[nx][ny][rot] = true;
                                dist[nx][ny][rot] = dist[x][y][rot] + 1;
                                if (map[nx][ny] == 'E' && map[nx-1][ny] == 'E' && map[nx+1][ny] == 'E') {
                                    if (ans > dist[nx][ny][rot]) { ans = dist[nx][ny][rot]; findd = true; }
                                }
                                q.push(P(nx, ny, rot));
                            }
                        }
                    }
            }
            else {
                if (rot == 0 && d[x][y][1] == false && x>0 && x<n-1 && (map[x + 1][y] == '0' || map[x + 1][y] == 'B' 
|| map[x + 1][y] == 'E') &&
                    (map[x - 1][y] == '0' || map[x - 1][y] == 'B' || map[x - 1][y] == 'E') &&(map[x + 1][y + 1] == '0'
 || map[x + 1][y + 1] == 'B' || map[x + 1][y + 1] == 'E') && (map[x - 1][y + 1] == '0' || map[x - 1][y + 1] == 'B' || map[x - 1][y + 1] == 'E')
                    && (map[x - 1][y - 1] == '0' || map[x - 1][y - 1] == 'B' || map[x - 1][y - 1] == 'E') && (map[x + 1][y - 1] == '0' || map[x + 1][y - 1] == 'B' || map[x + 1][y - 1] == 'E')) {
                    
                    d[x][y][1] = true;
                    dist[x][y][1] = dist[x][y][0] + 1;
                    if (x > 0 && x < n-1 && map[x][y] == 'E' && map[x - 1][y] == 'E' && map[x + 1][y] == 'E') {
                        if (ans > dist[x][y][1]) { ans = dist[x][y][1]; findd = true; }
                    }
                    q.push(P(x, y, 1));
                }
                else if (rot == 1 && d[x][y][0] == false && y>0 && y<n-1&&(map[x][y + 1] == '0' || map[x][y + 1] == 'B' || map[x][y + 1] == 'E') &&
                    (map[x][y - 1] == '0' || map[x][y - 1] == 'B' || map[x][y - 1] == 'E') && (map[x + 1][y + 1] == '0' || map[x + 1][y + 1] == 'B' || map[x + 1][y + 1] == 'E') && (map[x - 1][y + 1] == '0' || map[x - 1][y + 1] == 'B' || map[x - 1][y + 1] == 'E')
                    && (map[x - 1][y - 1] == '0' || map[x - 1][y - 1] == 'B' || map[x - 1][y - 1] == 'E') && (map[x + 1][y - 1] == '0' || map[x + 1][y - 1] == 'B' || map[x + 1][y - 1] == 'E')) {
                    d[x][y][0] = true;
                    dist[x][y][0] = dist[x][y][1] + 1;
                    if (y> 0 && y< n-1&&map[x][y] == 'E' && map[x][y - 1] == 'E' && map[x][y + 1] == 'E') {
                        if (ans > dist[x][y][0]) { ans = dist[x][y][0]; findd= true; }
                    }
                    q.push(P(x,y, 0));
                }
            }
        }
    }
    
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
    int cnt = 0;
    int ent = 0;
    int cx = 0, cy = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 'B') {
                cnt++;
                if (cnt == 2) {
                    cx = i; cy = j;
                }
            }
            if (map[i][j] == 'E') {
                ent++;
                if (ent == 2) {
                    ex = i; ey = j;
                }
            }
        }
    }
    int rot = 0;
    if (cx >= 1 && cx <n-1 && map[cx - 1][cy] == 'B' && map[cx + 1][cy] == 'B') {
        rot = 1;
    }
    else if (cy>= 1 && cy<n-1&& map[cx][cy + 1] == 'B' && map[cx][cy - 1] == 'B') {
        rot = 0;
    }
    bfs(cx, cy, rot);
    if (findd)
        cout << ans << '\n';
    else cout << 0 << '\n';
 
    
}

BFS문제, 어렵다 라기보다는 문제를 잘읽고풀어야한다는것이 좀더 기억에 남는 문제,

다른것보다도 돌아가는것을 3x3전체에 비어있어야한다는 조건을 잊고 돌려버리면 무조건틀리는문제다.