大佬求助14分。

P1228 地毯填补问题

zwb3_1415926 @ 2023-08-24 21:19:30

#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
int k,zx,zy;
bool vis[1025][1025],cnt;
bool fin(int bx,int ex,int by,int ey)
{
    int pd=0;
    for (int i=bx;i<=ex;i++)
        for (int j=by;j<=ey;j++) if (vis[i][j]) pd++;
    if (pd==0) return false;
    else return true;
}
void dfs(int bx,int ex,int by,int ey)
{
//  for (int i=1;i<=1<<k;i++)
//  {
//      for (int j=1;j<=1<<k;j++)
//      { 
//          if(vis[i][j]==true) cout<<1<<" ";
//          else cout<<0<<" ";
//      }
//      cout<<endl;
//  }
//  cout<<bx<<" "<<ex<<" "<<by<<" "<<ey<<endl;
//  cout<<endl<<endl;
//  Sleep(200);
    if (bx+1==ex&&by+1==ey)
    {
        int pd=0;
        for (int i=bx;i<=ex;i++)
            for (int j=by;j<=ey;j++) if (vis[i][j]) pd++;
        //cout<<pd<<endl;
        if (pd==4) return ;
        if (pd==0) return ;
        if ((bx==zx||ex==zx)&&(by==zy||ey==zy))
        {
            if (bx==zx&&by==zy) cout<<ex<<" "<<ey<<" "<<1<<endl;
            if (bx==zx&&ey==zy) cout<<ex<<" "<<by<<" "<<2<<endl;
            if (ex==zx&&by==zy) cout<<bx<<" "<<ey<<" "<<3<<endl;
            if (ex==zx&&ey==zy) cout<<ex<<" "<<by<<" "<<4<<endl;
            for (int i=bx;i<=ex;i++)
                for (int j=by;j<=ey;j++) vis[i][j]=true;
            return;
        }
        if (vis[bx][by]) 
        {
            for (int i=bx;i<=ex;i++)
                for (int j=by;j<=ey;j++) vis[i][j]=true;
            cout<<ex<<" "<<ey<<" "<<1<<endl;
            return;
        }
        if (vis[bx][ey])
        {
            for (int i=bx;i<=ex;i++)
                for (int j=by;j<=ey;j++) vis[i][j]=true;
            cout<<ex<<" "<<by<<" "<<2<<endl;
            return;
        }
        if (vis[ex][by]) 
        {
            for (int i=bx;i<=ex;i++)
                for (int j=by;j<=ey;j++) vis[i][j]=true;
            cout<<bx<<" "<<ey<<" "<<3<<endl;
            return;
        }
        if (vis[ex][ey])
        {
            for (int i=bx;i<=ex;i++)
                for (int j=by;j<=ey;j++) vis[i][j]=true;
            cout<<ex<<" "<<by<<" "<<4<<endl;
            return;
        }
        return ;
    }
    dfs(bx,(bx+ex)/2,by,(by+ey)/2);
    if (fin(bx,(bx+ex)/2,by,(by+ey)/2)&&!vis[(bx+ex)/2+1][(by+ey)/2+1])
    {
        cout<<(bx+ex)/2+1<<" "<<(by+ey)/2+1<<" "<<1<<endl;
        vis[(bx+ex)/2+1][(by+ey)/2]=true;vis[(bx+ex)/2][(by+ey)/2+1]=true;vis[(bx+ex)/2+1][(by+ey)/2+1]=true;
        dfs((bx+ex)/2+1,ex,by,(by+ey)/2);//左上 
        dfs(bx,(bx+ex)/2,(by+ey)/2+1,ey);
        dfs((bx+ex)/2+1,ex,(by+ey)/2+1,ey);
    }
    dfs(bx,(bx+ex)/2,(by+ey)/2+1,ey);
    if (fin(bx,(bx+ex)/2,(by+ey)/2+1,ey)&&!vis[(bx+ex)/2+1][(by+ey)/2])
    {
        cout<<(bx+ex)/2+1<<" "<<(by+ey)/2<<" "<<2<<endl;
        vis[(bx+ex)/2+1][(by+ey)/2+1]=true;vis[(bx+ex)/2][(by+ey)/2]=true;vis[(bx+ex)/2+1][(by+ey)/2]=true;
        dfs(bx,(bx+ex)/2,by,(by+ey)/2);//左上 
        dfs((bx+ex)/2+1,ex,by,(by+ey)/2);//左下 
        dfs((bx+ex)/2+1,ex,(by+ey)/2+1,ey);//右下 
    }
    dfs((bx+ex)/2+1,ex,by,(by+ey)/2);
    if (fin((bx+ex)/2+1,ex,by,(by+ey)/2)&&!vis[(bx+ex)/2][(by+ey)/2+1])
    {
        cout<<(bx+ex)/2<<" "<<(by+ey)/2+1<<" "<<3<<endl;
        vis[(bx+ex)/2][(by+ey)/2]=true;vis[(bx+ex)/2][(by+ey)/2+1]=true;vis[(bx+ex)/2+1][(by+ey)/2+1]=true;
        dfs(bx,(bx+ex)/2,by,(by+ey)/2);//左上 
        dfs(bx,(bx+ex)/2,(by+ey)/2+1,ey);//右上 
        dfs((bx+ex)/2+1,ex,(by+ey)/2+1,ey);//右下 
    }
    dfs((bx+ex)/2+1,ex,(by+ey)/2+1,ey);
    if (fin((bx+ex)/2+1,ex,(by+ey)/2+1,ey)&&!vis[(bx+ex)/2][(by+ey)/2])
    {
        cout<<(bx+ex)/2<<" "<<(by+ey)/2<<" "<<4<<endl;
        vis[(bx+ex)/2][(by+ey)/2]=true;vis[(bx+ex)/2][(by+ey)/2+1]=true;vis[(bx+ex)/2+1][(by+ey)/2]=true;
        dfs((bx+ex)/2+1,ex,by,(by+ey)/2);
        dfs(bx,(bx+ex)/2,(by+ey)/2+1,ey);
        dfs(bx,(bx+ex)/2,by,(by+ey)/2);//左上 
    }
    return;
}
int main()
{
    cin>>k>>zx>>zy;
    vis[zx][zy]=true;
    dfs(1,1<<k,1,1<<k);
}

|