#include "testlib.h"
#include <vector>

using namespace std;

// Directions for moving in 4 possible directions (up, down, left, right).
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

// Helper function to check if a cell (x, y) is within grid bounds.
bool inBounds(int x, int y, int n, int m) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// DFS-based maze generation to ensure connectivity between start and finish
void generateMaze(vector<vector<char>>& smallGrid, int sn, int sm, int sx, int sy) {
    vector<pair<int, int>> walls;
    smallGrid[sx][sy] = '.'; // Starting point is open

    // Add initial walls around the start point
    for (int i = 0; i < 4; i++) {
        int nx = sx + dx[i], ny = sy + dy[i];
        if (inBounds(nx, ny, sn, sm))
            walls.push_back({nx, ny});
    }

    // Process walls in randomized order
    while (!walls.empty()) {
        int idx = rnd.next(0, (int)walls.size() - 1);
        auto [x, y] = walls[idx];
        walls.erase(walls.begin() + idx);

        int openNeighbours = 0;

        // Count open path cells adjacent to this wall cell
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (inBounds(nx, ny, sn, sm) && smallGrid[nx][ny] == '.') {
                openNeighbours++;
            }
        }

        // Only carve out this wall if it connects to exactly one open path
        if (openNeighbours == 1) {
            smallGrid[x][y] = '.'; // Carve path

            // Add new walls around the newly carved path cell
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (inBounds(nx, ny, sn, sm) && smallGrid[nx][ny] == '#')
                    walls.push_back({nx, ny});
            }
        }
    }
}

// Function to expand the small grid into a larger grid with variable path widths
void expandGrid(const vector<vector<char>>& smallGrid, vector<vector<char>>& largeGrid, int kMin, int kMax) {
    int sn = smallGrid.size(), sm = smallGrid[0].size();

    for (int i = 0; i < sn; i++) {
        for (int j = 0; j < sm; j++) {
            if (smallGrid[i][j] == '.') {
                // Generate a random path width between 1 and k for corridors
                int pathWidth = rnd.next(kMin, kMax);

                // Ensure connectivity by expanding along the entire path row/column
                for (int di = 0; di < pathWidth; di++) {
                    for (int dj = 0; dj < pathWidth; dj++) {
                        int nx = i * kMax + di;
                        int ny = j * kMax + dj;
                        if (nx < largeGrid.size() && ny < largeGrid[0].size()) {
                            largeGrid[nx][ny] = '.';
                        }
                    }
                }

                // Additional connection to neighboring path cells to maintain connectivity
                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d];
                    int nj = j + dy[d];
                    if (inBounds(ni, nj, sn, sm) && smallGrid[ni][nj] == '.') {
                        int nx = ni * kMax;
                        int ny = nj * kMax;
                        int pathWidth = rnd.next(kMin, kMax);
                        // Carve a minimal 1-width path to connect neighboring cells
                        for (int dstep = 0; dstep < kMax; dstep++) {
                            if (dx[d] != 0) { // Vertical connection
                            	for (int cock = ny - pathWidth / 2; cock <= ny + pathWidth / 2; ++cock) {
                            		largeGrid[min(nx, nx - dx[d]) + dstep][clamp(cock, 0, (int)largeGrid[0].size())] = '.';
                            	}
                            } else { // Horizontal connection
                            	for (int cock = nx - pathWidth / 2; cock <= nx + pathWidth / 2; ++cock) {
                            		largeGrid[clamp(cock, 0, (int)largeGrid.size())][min(ny, ny - dy[d]) + dstep] = '.';
                            	}
                            }
                        }
                    }
                }
            }
        }
    }
}

int main(int argc, char* argv[]) {
    // Initialize testlib for generating random tests.
    registerGen(argc, argv, 1);
    
    std::cout << 1 << std::endl;

    int sn = atoi(argv[1]);
    int sm = atoi(argv[2]);
    int kMin = atoi(argv[3]);
    int kMax = atoi(argv[4]);
    // Define the grid dimensions and path width parameter k
    // int sn = rnd.next(5, 15); // Dimensions of the "small" maze grid
    // int sm = rnd.next(5, 15);
    // int k = rnd.next(2, 4); // Maximum width of each path in the maze

    // Ensure dimensions are odd for better maze generation.
    if (sn % 2 == 0) sn++;
    if (sm % 2 == 0) sm++;

    // Initialize the small grid with walls
    vector<vector<char>> smallGrid(sn, vector<char>(sm, '#'));

    // Choose random start and finish locations at opposite corners
    int sx = 1, sy = 1;
    int fx = sn - 2, fy = sm - 2;

    // Generate the maze with DFS, ensuring connectivity from start to finish
    generateMaze(smallGrid, sn, sm, sx, sy);

    // Determine the dimensions of the large grid
    int n = sn * kMax;
    int m = sm * kMax;

    // Initialize the large grid with walls
    vector<vector<char>> largeGrid(n, vector<char>(m, '#'));

    // Expand the small grid to the large grid with variable path widths
    expandGrid(smallGrid, largeGrid, kMin, kMax);

    std::vector<std::pair<int, int>> candidates;
    sx = -1, sy = -1;
    int tx = -1, ty = -1;
    for (int i = 0; i < n; ++i) {
    	for (int j = 0; j < m; ++j) {
    		if (largeGrid[i][j] == '#') {
    			continue;
    		}

    		int d1 = i + j;
    		int d2 = (n - i - 1) + (m - j - 1);
    		if (sx == -1 || sx + sy > d1) {
    			sx = i;
    			sy = j;
    		}
    		if (tx == -1 || (n - tx - 1) + (m - ty - 1) > d2) {
    			tx = i;
    			ty = j;
    		}
    	}
    }

    largeGrid[sx][sy] = 's';
    largeGrid[tx][ty] = 'f';
    // Set the start ('s') and finish ('f') cells in the large grid
    // largeGrid[sx * k + k / 2][sy * k + k / 2] = 's';
    // largeGrid[fx * k + k / 2][fy * k + k / 2] = 'f';

    // Output the large grid dimensions
    // println(n, m);
    std::cout << n << ' ' << m << std::endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // printf("%c", largeGrid[i][j]);
            std::cout << largeGrid[i][j];
        }
        std::cout << std::endl;
    }

    return 0;
}
