残缺棋牌-50行代码

        题目大致意思为给你一个大小为2^k大小的棋盘，这个棋盘残缺了一块，要求用数字按要求填满棋盘。假设给你4*4的棋盘，残缺的那一块坐标为1，1，则结果为

注意填充顺序为 中间->左上->右上->左下->右下。

解决此题的思路就是递归+分治，我们可以将棋盘分为四个象限，即将一个大小为 N*N 的正方形分为（N/2）*（N/2）的正方形，通过观察我们可以发现，当残缺的那一块在左上方区域时，中间的的区域是这样填充的：

填充完后，除了左上方本身有残缺的地方，我们在其他三个象限各自添加一个残缺的地方，即刚刚每个象限填充的坐标。

画圈的即表示残缺的地方，然后我们递归四个象限，每次递归只填充中间的区域，比如开始递归第一象限，残缺的在第二象限，我们只需把其他三个象限填充数字就行，然后因为这个象限已经填满数字了，所以无需进行递归下去，返回上一层递归第二、第三、第四象限。

代码如下：

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> >board;
int dir[]={0,0,1,1,1,0,1,0};//方向数组
int N,k,cx,cy;
void printboard()
{for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){printf("%3d",board[i][j]);}puts("");}
}
void process(int depth,int& diag,int wx,int wy,int bex,int bey)
{if(depth==0) { diag--;return;}int mid= 1<<(depth-1), flag=-1;int midx=mid+bex,midy=mid+bey;//找到中间的节点来分成4个象限if(wx<=midx&&wy<=midy) flag=0;else if(wx<=midx&&wy>midy) flag=1;else if(wx>midx&&wy<=midy) flag=2;else flag=3;int this_diag=diag;for(int i=0;i<4;i++){diag++;if(flag!=i)board[midx+dir[i]][midy+dir[7-i]]=this_diag; //如果残缺的地方不在此象限就涂上数字int next_x= flag==i? wx:midx+dir[i]; //已经有残缺的象限不需要更新，没有残缺的象限更新为涂上数字的坐标作为此象限残缺的地方int next_y= flag==i? wy:midy+dir[7-i];int start_x= (i==0||i==1) ? bex : bex+mid;//更新此递归的起始位置，即每个象限的左上角int start_y= (i==0||i==2) ? bey : bey+mid;process(depth-1,diag,next_x,next_y,start_x,start_y);}
}
int main()
{cin>>k>>cx>>cy; N=1<<k;board.resize(N+1,vector<int>(N+1));int diag=1;process(k,diag,cx,cy,0,0);diag++;printboard();
}