1263: 你会做蛋糕吗？（Java）

WUSTOJ 1263: 你会做蛋糕吗？

参考博客

Mitsuha_的博客

Description

        BobLee是个大吃货，喜欢吃好吃的，也喜欢做好吃的。比如做正方形的蛋糕。比如下图这个5*5的蛋糕。

      

        图中的*号是代表BobLee放在上面的草莓。不仅如此，BobLee还喜欢把蛋糕分给自己的好友，比如CMS,YYD,LCM,MCB他们吃。为了好看，分的时候每一块都是正方形的。现在BobLee想知道，能否将一个蛋糕分成几个正方形的小蛋糕（大于等于1个），并且每个蛋糕上面有且仅有一个草莓。

Input

        输入第一个为T，代表数据的组数
        每组测试数据的第一行是L(0 < L < 20)和N（N > 0），代表一个L*L的蛋糕中有N个草莓
        接下来是N行数字，每行是Xi和Yi，代表在（Xi，Yi）处有一个草莓。确保每处最多一个草莓。

Output

        如果可以满足要求就输出YES，如果不可以请输出NO

Sample Input

1
5 8
2 5
3 3
3 4
3 5
4 2
4 4
4 5
5 5

Sample Output

YES

题目分析

        这道题我本来以为只是一个简单搜索的题目，然后等代码写完，才发现，我那种只是从左上向右下的简单搜索，根本就没考虑到所有的情况。于是就找到了参考的那篇博客。
        其实这道题是一个彻头彻尾的回溯题目，沿着某一种情况向下寻找判断，不合要求就恢复到原状态并继续循环查找下一个。
        直到所有小块蛋糕（有草莓和无草莓）都被切之后，即表明找到了（成功）。一旦在中途发现有一小块蛋糕无法分配到任何可切的部分，则不满足要求（失败）。

代码

/**
 * 用时：406ms
 * @author wowpH
 * @version A2.0
 * @date 2019年4月13日 上午10:44:09
 */

import java.util.Scanner;

public class Main {

	private Scanner sc;
	private int T, L, N, Xi, Yi; // 输入数据
	/**
	 * @Field cake</br>
	 * 0表示小块蛋糕，没被切</br>
	 * 1表示有草莓的小块蛋糕，没被切</br>
	 * 2表示小块蛋糕，已切</br>
	 * 3表示有草莓的小块蛋糕，已切</br>
	 */
	private int[][] cake; // 整个蛋糕

	public Main() {
		sc = new Scanner(System.in);
		boolean flag;	// 是否能切成功
		T = sc.nextInt();	// 整个蛋糕尺寸
		while (T > 0) {
			L = sc.nextInt();
			N = sc.nextInt();
			cake = new int[L + 1][L + 1]; // 下标从1开始
			while (N > 0) {
				Xi = sc.nextInt();
				Yi = sc.nextInt();
				cake[Xi][Yi] = 1; // 1表示草莓，0表示蛋糕
				N--; // 剩余草莓个数减1
			}
			// 切蛋糕
			flag = false;	// 初始不能满足要求
			for (int i = 0; i < L; i++) {
				if (cutCake(1, 1, i)) {
					flag = true;	// 满足要求，退出循环
					break;
				}
			}
			if(flag) {
				System.out.println("YES");	// 满足要求输出YES
			} else {
				System.out.println("NO");	// 不满足输出NO
			}
			T--;	// 剩余数据减1
		}
		sc.close();
	}

	/**
	 * @param x	行
	 * @param y	列
	 * @param offset	偏移量
	 * @return	当前区域切蛋糕是否成功
	 */
	private boolean cutCake(int x, int y, int offset) {
		int maxX, maxY;
		maxX = x + offset;
		maxY = y + offset;
		// 查找(x, y)右下offset内是否只能找到1个草莓
		// 没有草莓或者不止1个草莓，都不符合要求，返回切蛋糕失败
		if(false == findStrawberry(x, y, offset)) {
			return false;
		}
		// 这片蛋糕符合要求，切下来
		cut(x, y, offset);
		// 查找剩余的没被切（cake为0或1）的位置
		for(int i = 1; i <= L; i++) {
			for(int j = 1; j <= L; j++) {
				// 是没切的蛋糕或者没切的草莓
				if(0 == cake[i][j] || 1 == cake[i][j]) {
					// 从这1点向右下遍历，前提是不能超出整个蛋糕的范围
					for(int k = 0; k <= L - i && k <= L - j; k++) {
						// 内层切蛋糕成功
						if(cutCake(i, j, k)) {
							return true;	// 说明这当前区域能切成功，返回成功
						}
					}
					// 内层切蛋糕失败，并且此时这里有1小块（即[i, j]）没被切的不能分配，
					// 因此当前区域切蛋糕失败，由于当前区域之前切了，
					// 因此需要恢复为没被切的状态，并返回失败
					// 回溯算法的关键点就在这里
					for(int p = x; p <= maxX; p++) {
						for(int q = y; q <= maxY; q++) {
							cake[p][q] -= 2;
						}
					}
					// 按照当前切法，下层有蛋糕不能正常切割，当前切法不合理，返回失败
					return false;
				}
			}
		}
		return true; // 没有多余的地方没切到，则切蛋糕成功
	}
	
	/**
	 * @param x	行
	 * @param y	列
	 * @param offset	偏移量
	 * @return	只有1个草莓返回true，0个草莓或者不止1个草莓返回false
	 */
	private boolean findStrawberry(int x, int y, int offset) {
		int strawberry = 0; // 草莓个数，初始为0个
		int maxX, maxY;
		maxX = x + offset;
		maxY = y + offset;
		for (int i = x; i <= maxX; i++) {
			for (int j = y; j <= maxY; j++) {
				if (1 == cake[i][j]) {
					strawberry++; // 草莓数加1
					// 草莓数量已经不止1个了，显然是不合理的，直接返回不能切蛋糕
					if(strawberry > 1) {
						return false;
					}
				} else if(0 != cake[i][j]) {
					// 不是草莓，也不是没被切的蛋糕，说明这里已经切到其他草莓块了
					return false;
				}	// 是0的话继续
			}
		}
		if(0 == strawberry) {
			return false;	// 这片区域没有草莓，不符合要求，返回不能切蛋糕
		}		
		return true;	// 默认这里可以切蛋糕
	}
	
	/**
	 * 将蛋糕的这片区域设置为已切
	 * @param x	行
	 * @param y	列
	 * @param offset	偏移量
	 */
	private void cut(int x, int y, int offset) {
		int maxX, maxY;
		maxX = x + offset;
		maxY = y + offset;
		for(int i = x; i <= maxX; i++) {
			for(int j = y; j <= maxY; j++) {
				cake[i][j] += 2;	// 变成已切的
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new Main();
	}

}

查漏补缺

        下面这个错误是因为输入流已经没有数据了，而程序还在读取数据（例如：sc.nextInt()，sc.nextDouble()等等）。

Exception in thread "main" java.util.NoSuchElementException

        我错的原因是循环末尾T没有减1（第50行），然后无限循环，输入流已经没数据了，但是我的（第28行）又读取了，显然是不可能读取到数据的，因此报错。
        避免的方法是：写循环体的第一步就把减1写出来，免得后来忘了。——粗心的wowpH

---

写在最后：

1. 如需转载，请于标题下注明链接形式的wowpH的博客即可；
2. 代码原创，如需公开引用，不能删除首行注释（作者，版本号，时间等信息）。

---