BOJ 17500

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

char map[MAXN][MAXN];
bool visited[MAXN][MAXN];
bool check[MAXN][MAXN];

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N;
bool flag = false;
bool possible;
bool is_range(int x, int y){
    return (x>= 2 && y >= 3 && x < 2*N+1 && y< 4*N+1);
}
void bfs(int x, int y, char target){
    queue<pair<int,int> > q;
    q.push({x,y});
    check[x][y] = true;
    while (!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int k = 0; k< 4; k++){
            int nx = x + dx[k];
            int ny = y + 2*dy[k];
            int nx1 = x + 2*dx[k];
            int ny1 = y + 4*dy[k];
            if (map[nx][ny] == '-' || map[nx][ny] == '|') continue;
            if (!is_range(nx1,ny1) || check[nx1][ny1]) continue;
            if (map[nx1][ny1] != '.' && map[nx1][ny1] != target){
                possible = true;
                return;
            }
            else{
                check[nx1][ny1] = true;
                q.push({nx1,ny1});
            }
        }
    }
}
void backtrack(int x, int y){
    if (flag) return;
    if (x == 2*N+1 && y == 4*N+1){
        possible = false;
        memset(check,false,sizeof(check));

        for (int i = 2; i < 2*N+2 && !possible; i+=2){
            for (int j=3 ; j< 4*N+2; j+=4){
                if (!check[i][j] && map[i][j] != '.'){
                    bfs(i,j,map[i][j]);
                }
            }
        }
        if (!possible){
            cout <<"yes\n";
            for (int i =0 ; i < 2*N+3; i++){
                for (int j=0 ;j<4*N+3; j++){
                    cout << map[i][j];
                }
                cout <<"\n";
            }
            flag = true;
        }
        return;
    }
    if (visited[x][y]) return;
    for (int k = 0; k< 4; k++){
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (map[nx][ny] == '#' || map[nx][ny] != ' ') continue;
        visited[x][y] = true;
        while (map[nx][ny] != '+'){
            if (k < 2) map[nx][ny] = '-';
            else map[nx][ny] = '|';
            nx += dx[k];
            ny += dy[k];
        }
        backtrack(nx,ny);
        nx -= dx[k];
        ny -= dy[k];
        while (map[nx][ny]!='+'){
            map[nx][ny] = ' ';
            nx -= dx[k];
            ny -= dy[k];
        }
        visited[x][y] = false;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i <2*N+3; i++){
        for (int j = 0 ;j < 4*N+3; j++){
            if (i == 0 || i == 2*N+2 || j == 0 || j == 4*N+2) map[i][j] = '#';
            else map[i][j] =' ';
        }
    }
    for (int i = 1; i < 2*N+2; i+=2){
        for (int j = 1; j < 4*N+2; j+=4){
            map[i][j] = '+';
        }
    }
    for (int i = 2; i < 2*N+2; i+=2){
        for (int j=3; j<4*N+2; j+=4){
            cin >> map[i][j];
        }
    }
    backtrack(1,1);
    if (!flag) cout << "no\n";
    return 0;
}