分治法解决残缺棋盘

分治法解决残缺棋盘

问题描述

给定$2^k\times 2^k$的棋盘，其中有一个残缺的格子，其他的格子都不是残缺的，请给出一种方案用三格板拼成该棋盘。

三格板有以下4种：(红色部分为残缺)

思路

考虑用分治法解决。

在二位棋盘上，我们假设左上角的坐标为$(x_1,y_1)$，残缺块的位置为$(x_g,y_g)$

当前棋盘的边长为：$len$

我们将其四等分：左上，右上，左下，右下。

• 首先找到残缺块属于哪一个部分。
• 对该部分进行递归解决
• 对剩下三个部分分别填入一个残缺块，即相当于填一个三格板。
• 递归解决剩下三个部分。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int gx,gy;
int num;
int a[N][N];
void paint(int x,int y,int k){++num;int c=0;for(int i=0;i<2;i++)for(int j=0;j<2;j++){c++;if(c==k) continue;a[x+i][y+j]=num;}
}
void fun(int x,int y,int len){if(len==1) return;int k=len>>1;if(gx<x+k&&gy<y+k){	//左上 fun(x,y,k);paint(x+k-1,y+k-1,1);fun(x,y+k,k);fun(x+k,y,k);fun(x+k,y+k,k);}else if(gx<x+k&&gy>=y+k){	//右上 fun(x,y+k,k);paint(x+k-1,y+k-1,2);fun(x,y,k);fun(x+k,y,k);fun(x+k,y+k,k);}else if(gx>=x+k&&gy<y+k){	//左下 fun(x+k,y,k);paint(x+k-1,y+k-1,3);fun(x,y,k);fun(x,y+k,k);fun(x+k,y+k,k);}else{	//右下 fun(x+k,y+k,k);paint(x+k-1,y+k-1,4);fun(x,y,k);fun(x,y+k,k);fun(x+k,y,k);}
}
int main(){int k;scanf("%d%d%d",&k,&gx,&gy);int s=1;while(k--) s<<=1;fun(1,1,s);for(int i=1;i<=s;i++){for(int j=1;j<=s;j++) printf("%d",a[i][j]);printf("\n");}return 0;
} 

运行结果

例题

描述运用分治法解决残缺棋盘的思路。