Blue Bridge Cup - Stamp cutting (Group 10, Java B, 2016)

Stamp cutting (16JavaB10)

As shown in Figure 1, there are 12 stamps of the Chinese zodiac.
Now you have to cut five of them. They must be connected.
(connecting only one corner is not connected)
For example, in [figure 2] and [figure 3], the part shown in pink is the qualified cutting.

Please calculate how many different cutting methods there are.

problem analysis

By topic, counting from 1:
|-Peer: (id-1) ÷ 4 results are equal, left and right neighbors: subtract ± 1
|-The results of the same column:% 4 are the same, the upper and lower neighbors: subtract ± 4

Using depth first traversal,

Depth first: push to the end, touch the bottom again

For example: {3,5,6,7,10}

First, find out who is next to {3,5,6,7,10}:
3-X
5-X
6-X
7-OK
10- waiting

Match 3-7, continue to push forward, compare 7 and who is adjacent (3 has been compared, it is not matched):
3-X
5-X
6-OK
7- waiting
10- waiting

Match 7-6, continue to push forward, compare 6 with who is next:
3-X
5-OK
6- waiting
7- waiting
10- waiting

Although 6 and 10 pages are adjacent, the "depth first" is advanced first, regardless of 10.
5 is no longer adjacent, so go back to 6 and match to 10.

Deep recursion:
|-Push to the end first, and then turn around.
|-As long as every point can be reached, it means it's connected.

package bb;
import java.util.HashSet;
import java.util.Set;
public class Cutting stamps {
	private static boolean check(int a[]) {
		boolean flag[] = new boolean[5];
		dfs(a, flag, 0);
		return flag[0] && flag[1] && flag[2] && flag[3] && flag[4];
	}
	// Depth first search
	private static void dfs(int a[], boolean[] flag, int n) {
		flag[n] = true;
		for (int i = 0; i < 5; i++) {
			// Peer: (id-1) ÷ 4 results are equal, left and right neighbors: add and subtract to 1
			// You can't use ÷ 5. There are four in one line (9 ÷ 5 = = 1, 10 ÷ 5 = = 2)
			if (!flag[i] && ((a[i] - 1) / 4 == (a[n] - 1) / 4)
					&& (a[i] == a[n] - 1 || a[i] == a[n] + 1)) {
				dfs(a, flag, i);
			}
			// The results of the same column:% 4 are the same, the upper and lower neighbors: add and subtract to 4
			if (!flag[i] && (a[i] % 4 == a[n] % 4) && (a[i] == a[n] - 4 || a[i] == a[n] + 4)) {
				dfs(a, flag, i);
			}
		}
	}
	static Set<String> cutStamps() {
		int[] a = new int[5];
		Set<String> _set = new HashSet<String>();
		int START = 0 + 1;
		int END = 12 + 1;
		for (a[0] = START; a[0] < END; ++a[0]) {
			for (a[1] = a[0] + 1; a[1] < END; ++a[1]) {
				for (a[2] = a[1] + 1; a[2] < END; ++a[2]) {
					for (a[3] = a[2] + 1; a[3] < END; ++a[3]) {
						for (a[4] = a[3] + 1; a[4] < END; ++a[4]) {
							if (check(a)) {
								_set.add("" + a[0] + " " + a[1] + " " + a[2] + " " + a[3] + " "
										+ a[4]);
							}
						}
					}
				}
			}
		}
		return _set;
	}
	public static void main(String[] args) {
		Set<String> _set1 = cutStamps();
		System.out.println(_set1.size());
		System.out.println(_set1.contains("2 6 7 11 12"));
		System.out.println(_set1.contains("3 5 6 7 10"));
	}
}

Tags: Java

Posted on Sat, 02 Nov 2019 05:16:57 -0700 by big-dog1965