Tiling Problem/Defective chessboard problem

#include<bits/stdc++.h>
using namespace std;

int team[500][500],cnt=1,m;

void room(int x1, int y1, int X, int Y, int nx, int ny)
{
    if(cnt > m)return;
    if(abs(x1 - nx) <= 1 && abs(y1 - ny)<= 1){
        for(int i = x1; i <= nx; i++){
            for(int k  = y1; k <= ny; k++){
                if(team[i][k] == 0)team[i][k] = cnt;
            }
        }
        cnt++;
        return;
    }

    int mid_x = (x1+nx)/2;
    int mid_y = (y1+ny)/2;
    //cnt++;
    if(X > mid_x){///lower
        if(Y > mid_y){

            ///lower_right
            //cnt++;
            team[mid_x][mid_y] = cnt;
            team[mid_x][mid_y+1] = cnt;
            team[mid_x+1][mid_y] = cnt;
            cnt++;

        room(x1, y1, mid_x, mid_y, mid_x, mid_y);
        room(x1, mid_y+1, mid_x, mid_y+1, mid_x, ny);
        room(mid_x+1,y1, mid_x+1, mid_y, nx, mid_y);
        room(mid_x+1, mid_y+1, X, Y, nx, ny);

        }
        else{
            ///lower_left
           // cnt++;
            team[mid_x][mid_y] = cnt;
            team[mid_x][mid_y+1] = cnt;
            team[mid_x+1][mid_y+1] = cnt;
            cnt++;

        room(x1, y1, mid_x, mid_y, mid_x, mid_y);
        room(x1, mid_y+1, mid_x, mid_y+1, mid_x, ny);
        room(mid_x+1,y1, X, Y, nx, mid_y);
        room(mid_x+1, mid_y+1, mid_x+1, mid_y+1, nx, ny);

        }
    }
    else{///upper
        if(Y > mid_y){
            ///upper_right
            //cnt++;
            team[mid_x][mid_y] = cnt;
            team[mid_x+1][mid_y] = cnt;
            team[mid_x+1][mid_y+1] = cnt;
            cnt++;

        room(x1, y1, mid_x, mid_y, mid_x, mid_y);
        room(x1, mid_y+1, X, Y, mid_x, ny);
        room(mid_x+1,y1, mid_x+1, mid_y, nx, mid_y);
        room(mid_x+1, mid_y+1, mid_x+1, mid_y+1, nx, ny);

        }
        else{
            ///upper_left
            //cnt++;
            team[mid_x+1][mid_y] = cnt;
            team[mid_x][mid_y+1] = cnt;
            team[mid_x+1][mid_y+1] = cnt;
            cnt++;
        room(x1, y1, X, Y, mid_x, mid_y);
        room(x1, mid_y+1, mid_x, mid_y, mid_x, ny);
        room(mid_x+1,y1, mid_x+1, mid_y, nx, mid_y);
        room(mid_x+1, mid_y+1, mid_x+1, mid_y+1, nx, ny);
        }

    }
    return;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif

    int sz;
    cin >> m;
/// here m is the total team number.
    int  ck = m*3 + 1;
    for(int  i = 0; i <32; i++){
        int valid = 1 << i;
        int  ckk= valid*valid;
        if(ckk >= ck){
            sz = valid;
            break;
        }
    }
    cout << sz << endl;
    int X = rand()%sz;
    int Y = rand()%sz;
    //cout << X << " "<<Y<<endl;
    team[X][Y] = -1;
    room(1,1,X,Y,sz,sz);
   // cout << "ENter----------"<<endl;
    for(int i = 1; i <= sz; i++){
        for(int k = 1; k <= sz; k++){
            if(i==X&&k==Y)cout << setw(5)<<"X";
            else
            cout << setw(5)<<team[i][k];
        }
        cout << endl;
    }
    return 0;

}

Share: