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

1
2
3
4
5
6
7
8
9
10
11
1
5 8
2 5
3 3
3 4
3 5
4 2
4 4
4 5
5 5

Sample Output

复制代码YES

1
2
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(); } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/**
 * 用时：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

1
2
Exception in thread "main" java.util.NoSuchElementException

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

---

写在最后：

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

---