BOJ 14451

#include <iostream>
#include <queue>
using namespace std;
#define MAXN 20

int dist[MAXN][MAXN][MAXN][MAXN][4][4];
char map[MAXN][MAXN];
int N;
struct node{
    int x1;
    int y1;
    int x2;
    int y2;
    int dir1;
    int dir2;
};
queue<node> q;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int dirs[3] = {-1,0,1};
int bfs(){
    q.push({N-1,0,N-1,0,3,0});
    dist[N-1][0][N-1][0][3][0] = 1;
    int time = 0;
    while (!q.empty()){
        int q_size=  q.size();
        int x1 = q.front().x1;
        int y1 = q.front().y1;
        int x2 = q.front().x2;
        int y2 = q.front().y2;
        int dir1 = q.front().dir1;
        int dir2 = q.front().dir2;
        if (x1 == 0 && x2 == 0 && y1 == N-1 && y2 == N-1) {
            return dist[x1][y1][x2][y2][dir1][dir2]-1;
        }
        q.pop();
        for (int i = 0;i < 3; i++){
            int ndir1 = dir1;
            int ndir2 = dir2;
            int nx1 = x1;
            int ny1 = y1;
            int nx2 = x2;
            int ny2 = y2;
            if (!(x1 == 0 && y1 == N-1)){
                ndir1 = (4 + dir1 + dirs[i])%4;
                if (ndir1 == dir1){
                    nx1 += dx[dir1];
                    ny1 += dy[dir1];
                    if (nx1 < 0 || ny1 < 0 || nx1 >= N || ny1 >=N || map[nx1][ny1] == 'H'){
                        nx1 -= dx[dir1];
                        ny1 -= dy[dir1];
                    }
                }
            }
            if (!(x2 == 0 && y2 == N-1)){
                ndir2 = (4+ dir2 + dirs[i])%4;
                if (ndir2 == dir2){
                    nx2 += dx[dir2];
                    ny2 += dy[dir2];
                    if (nx2 < 0 || ny2 < 0 || nx2 >= N || ny2 >=N || map[nx2][ny2] == 'H'){
                        nx2 -= dx[dir2];
                        ny2 -= dy[dir2];
                    }
                }
            }
            if (dist[nx1][ny1][nx2][ny2][ndir1][ndir2]) continue;
            dist[nx1][ny1][nx2][ny2][ndir1][ndir2] = dist[x1][y1][x2][y2][dir1][dir2]+1;
            q.push({nx1,ny1,nx2,ny2,ndir1,ndir2});
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0 ;i  <N;i++){
        for (int j =0;j<N;j++){
            cin >> map[i][j];
        }
    }
    cout << bfs();
    return 0;
}