AOJ.859 地毯填补问题 (递归与分治)

题意分析

学习分治思想，第一次接触，

代码总览

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <sstream>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <cmath>

#define INF 0x3f3f3f3f

#define nmax 200

#define MEM(x) memset(x,0,sizeof(x))

using namespace std;

int k;

void work(int x,int y,int l,int temp,int fx,int fy)

{

     if(temp==1){

        if(fx==x && fy==y){

             printf("%d %d %d\n",fx+1,fy+1,1);

             return;

        }

        if(fx==x && fy!=y){

            if(fx+1==7 && fy-1==2)

                fx=6;

                printf("%d %d %d\n",fx+1,fy-1,2);

                return;

        }

        if(fx!=x && fy==y){

            printf("%d %d %d\n",fx-1,fy+1,3);

            return;

        }

        printf("%d %d %d\n",fx-1,fy-1,4);return;

     }

     int nx,ny,nl=l/2;

     nx=x+nl;

     ny=y+nl;

     if(fx>=x && fx<nx && fy>=y && fy<ny){

         printf("%d %d %d\n",nx,ny,1);

         work(x,y,nl,temp-1,fx,fy);

         work(x,ny,nl,temp-1,nx-1,ny);

         work(nx,y,nl,temp-1,nx,ny-1);

         work(nx,ny,nl,temp-1,nx,ny);

         return;

     }

    if(fx>=x && fx<nx && fy>=ny){

         printf("%d %d %d\n",nx,ny-1,2);

         work(x,y,nl,temp-1,nx-1,ny-1);

         work(x,ny,nl,temp-1,fx,fy);

         work(nx,y,nl,temp-1,nx,ny-1);

         work(nx,ny,nl,temp-1,nx,ny);

         return;

    }

    if(fx>=nx && fy>=y && fy<ny){

         printf("%d %d %d\n",nx-1,ny,3);

         work(x,y,nl,temp-1,nx-1,ny-1);

         work(x,ny,nl,temp-1,nx-1,ny);

         work(nx,y,nl,temp-1,fx,fy);

         work(nx,ny,nl,temp-1,nx,ny);

         return;

    }

    printf("%d %d %d\n",nx-1,ny-1,4);

    work(x,y,nl,temp-1,nx-1,ny-1);

    work(x,ny,nl,temp-1,nx-1,ny);

    work(nx,y,nl,temp-1,nx,ny-1);

    work(nx,ny,nl,temp-1,fx,fy);

    return;

}

int main ()

{

     //freopen("in.txt","r",stdin);

     int x,y,len =1,i;

     scanf("%d",&k);

     scanf("%d %d",&x,&y);

     i = k;

     while (i--) len*=2;

     work(1,1,len,k,x,y);

}