[数据结构与算法]P1228 地毯填补问题（Java语言实现）

输入输出样例见原题链接：地毯填补问题 - 洛谷

这道题属于分治算法经典问题棋盘覆盖问题的衍生题。为了更好的讲解解题思路，在这里我将举一个例子，通过例子来说明，如下图，黑色方块为公主位置，其他颜色则为毛毯。

? ? ? ?

? ? ? ? 1，将大方块分成四小块，找到被公主覆盖的位置在哪个小块 。

????????2，在该小块顶角铺上填补此形状的毛毯，使公主不在的三个小方块各被覆盖一个位置。

? ? ? ? 3，进入公主所在的方块，重复上述操作。直到被填满。

? ? ? ? 4，由于公主不在的方块未被处理，且因为公主不在的三个方块被覆盖了一个位置，所以可以把毛毯覆盖的位置看做是公主所在的位置，重复上述操作，直到被填满。

??????

动态图演示

静态原图来源:

棋盘覆盖问题-分治法_死啦死啦滴的博客-CSDN博客_棋盘覆盖

接下来是Java代码，注意其中的细节

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k,x,y;
		k=sc.nextInt();
		x=sc.nextInt();
		y=sc.nextInt();
		fill(x,y,1,1,1<<k);//位运算，等同于2的k次方
		sc.close();
	}
	 static void fill(int x,int y,int dx,int dy,int len) {
		if(len==1) {
			return;
		}
		len>>=1;//等同于len÷=2
		//公主在左上
		 if(x-dx<len&&y-dy<len) {
			System.out.println((dx+len)+" "+(dy+len)+" "+1);
			fill(x,y,dx,dy,len);//公主所在区域继续分块
			fill(dx+len-1,dy+len,dx,dy+len,len);//右上进行分块
			fill(dx+len,dy+len-1,dx+len,dy,len);//左下进行分块
			fill(dx+len,dy+len,dx+len,dy+len,len);//右下进行分块
		}
		//公主在右上
		 else if(x-dx<len&&y-dy>=len) {
			System.out.println((dx+len)+" "+(dy+len-1)+" "+2);
			fill(x,y,dx,dy+len,len);//公主所在区域继续分块
			fill(dx+len-1,dy+len-1,dx,dy,len);//左上进行分块
			fill(dx+len,dy+len-1,dx+len,dy,len);//左下进行分块
			fill(dx+len,dy+len,dx+len,dy+len,len);//右下进行分块
		}
		//公主在左下
		 else if(x-dx>=len&&y-dy<len) {
			System.out.println((dx+len-1)+" "+(dy+len)+" "+3);
			fill(x,y,dx+len,dy,len);//公主所在区域继续分块
			fill(dx+len-1,dy+len-1,dx,dy,len);//左上进行分块
			fill(dx+len-1,dy+len,dx,dy+len,len);//右上进行分块
			fill(dx+len,dy+len,dx+len,dy+len,len);//右下进行分块
		}
		//公主在右下
		 else if(x-dx>=len&&y-dy>=len) {
			System.out.println((dx+len-1)+" "+(dy+len-1)+" "+4);	
			fill(x,y,dx+len,dy+len,len);//公主所在区域继续分块
			fill(dx+len-1,dy+len-1,dx,dy,len);//左上进行分块
			fill(dx+len-1,dy+len,dx,dy+len,len);//右上进行分块
			fill(dx+len,dy+len-1,dx+len,dy,len);//左下进行分块
		}
	}

}