Walls

struct Wall {
    int y;
    int x;
    int component_number;
};

void MarkComponents(std::vector<std::vector<int>>& maze, const std::vector<std::pair<int, int>>& dirs, std::queue<Wall>* const walls) {
    const int m = maze.size();
    const int n = maze[0].size();

    std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));

    int set_number = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (maze[i][j] != '.' || visited[i][j]) {
                continue;
            }
            visited[i][j] = true;

            --set_number;

            std::queue<std::pair<int, int>> q;
            q.push({i, j});
            while (!q.empty()) {
                const auto cur = q.front();
                q.pop();

                maze[cur.first][cur.second] = set_number;

                for (const auto dir : dirs) {
                    const auto y = cur.first + dir.first;
                    const auto x = cur.second + dir.second;

                    if (y < 0 || y >= m || x < 0 || x >= n || visited[y][x]) {
                        continue;
                    }
                    visited[y][x] = true;

                    if (maze[y][x] == '.') {
                        q.push({y, x});
                    } else if (y > 0 && y < m-1 && x > 0 && x < n-1 && maze[y][x] != '+') {
                        walls->push({y, x, set_number});
                    }
                }
            }
        }
    }
}

bool DFS(std::vector<std::vector<int>>& maze, int start_component, std::pair<int, int> cur, std::vector<std::vector<bool>>& visited, const std::vector<std::pair<int, int>>& dirs) {
    const auto m = maze.size();
    const auto n = maze[0].size();

    if (maze[cur.first][cur.second] < 0) {
        const auto cur_component = maze[cur.first][cur.second];
        if (cur_component == start_component) {
            return false;
        }

        std::queue<std::pair<int, int>> q;
        q.push({cur.first, cur.second});
        while (!q.empty()) {
            const auto cur_node = q.front();
            q.pop();

            if (visited[cur_node.first][cur_node.second]) {
                continue;
            }
            visited[cur_node.first][cur_node.second] = true;
            maze[cur_node.first][cur_node.second] = start_component;

            for (const auto dir : dirs) {
                const auto y = cur_node.first + dir.first;
                const auto x = cur_node.second + dir.second;
                if (y < 0 || y >= m || x < 0 || x >= n || maze[y][x] > 0 || maze[y][x] == start_component) {
                    continue;
                }
                q.push({y, x});
            }
        }
        return true;
    }

    visited[cur.first][cur.second] = true;

    for (const auto dir : dirs) {
        const auto y = cur.first + dir.first;
        const auto x = cur.second + dir.second;

        if (y <= 0 || y >= m-1 || x <= 0 || x >= n-1 || maze[y][x] == '+' || visited[y][x]) {
            continue;
        }

        if (DFS(maze, start_component, {y, x}, visited, dirs)) {
            maze[cur.first][cur.second] = start_component;
            return true;
        }
    }
    return false;
}

void RemoveWalls(std::vector<std::vector<int>>& maze, const std::vector<std::pair<int, int>>& dirs, std::queue<Wall>* const walls) {
    std::vector<std::vector<bool>> visited(maze.size(), std::vector<bool>(maze[0].size(), false));

    while (!walls->empty()) {
        const auto cur = walls->front();
        walls->pop();

        DFS(maze, cur.component_number, {cur.y, cur.x}, visited, dirs);
    }
}

void Maze() {
    int n, m;
    std::cin >> n >> m;
    n  = 2 * n + 1;
    m = 2 * m + 1;
    std::vector<std::vector<int>> maze(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char ch;
            std::cin >> ch;
            maze[i][j] = ch;
        }
    }

    const std::vector<std::pair<int, int>> dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    std::queue<Wall> walls;
    MarkComponents(maze, dirs, &walls);
    RemoveWalls(maze, dirs, &walls);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (maze[i][j] < 0) {
                std::cout << '.';
            } else {
                std::cout << static_cast<char>(maze[i][j]);
            }
        }
        std::cout << std::endl;
    }
}