分治

每次将当前正方形分成四个小正方形，令公主所在格为特殊格点。在正方形中心放一个 L 形，其缺口正对有特殊格点的小正方形，然后标记这个 L 形的三个方格为特殊格点，按此方法分治。

时间复杂度 $O(2^k)$。

#include<bits/stdc++.h>
using namespace std;
int k,prinx,priny;
void run(int lx,int ly,int rx,int ry,int px,int py){
    if(lx==rx) return;
    int mx=lx+rx>>1,my=ly+ry>>1;//中心地毯铺在(mx,my)->(mx+1,my+1)
    if(px<=mx){//左半边
        if(py<=my){//上半边
            printf("%d %d 1\n",mx+1,my+1);
            run(lx,ly,mx,my,px,py);
            run(lx,my+1,mx,ry,mx,my+1);
            run(mx+1,ly,rx,my,mx+1,my);
            run(mx+1,my+1,rx,ry,mx+1,my+1);
        }
        else{//下半边
            printf("%d %d 2\n",mx+1,my);
            run(lx,ly,mx,my,mx,my);
            run(lx,my+1,mx,ry,px,py);
            run(mx+1,ly,rx,my,mx+1,my);
            run(mx+1,my+1,rx,ry,mx+1,my+1);
        }
    }
    else{//右半边
        if(py<=my){//上半边
            printf("%d %d 3\n",mx,my+1);
            run(lx,ly,mx,my,mx,my);
            run(lx,my+1,mx,ry,mx,my+1);
            run(mx+1,ly,rx,my,px,py);
            run(mx+1,my+1,rx,ry,mx+1,my+1);
        }
        else{//下半边
            printf("%d %d 4\n",mx,my);
            run(lx,ly,mx,my,mx,my);
            run(lx,my+1,mx,ry,mx,my+1);
            run(mx+1,ly,rx,my,mx+1,my);
            run(mx+1,my+1,rx,ry,px,py);
        }
    }
}
int main(){
    scanf("%d%d%d",&k,&prinx,&priny);
    run(1,1,1<<k,1<<k,prinx,priny);
    return 0;
}