【回溯】B041_LQ_剪邮票（dfs + 全排列 + 去重）

一、Problem

如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

116

二、Solution

尝试一：暴搜

错误思路：

• 以每一个格子作为起点跑一下 dfs。
• 最后去重一下即可。

局限性：深搜是一个方向，然后从后面的格子回退，回退时记录的步数也会被撤回，故不适合…

方法二：全排列 + dfs

• 注意基于交换的全排列会导致结果重复，所以需要对全排列的结果进行去重。
• 每次得到一个全排列，就去判断选中的邮票是否是连通即可。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
	static int[] a = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
	static boolean[] vis;
	static int[][] mp;
	static int res;
	static int R = 3, C = 4, N = 12;
	final static int[][] dir = { {1,0},{0,-1},{0,1},{-1,0} };
	
	static boolean check(int[] stp) {
    	mp = new int[R][C];
		for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			if (stp[i*C+j] == 1)mp[i][j] = 1;
			else 			    mp[i][j] = 0;
		}
		int cnt = 0;
		for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			if (mp[i][j] == 1) {
				dfs(i, j);
				cnt++;
			}
		}
		return cnt == 1;
	}
	static void dfs(int x, int y) {
		for (int k = 0; k < 4; k++) {
			int tx = x + dir[k][0];
			int ty = y + dir[k][1];
			if (tx < 0 || tx >= R || ty < 0 || ty >= C || mp[tx][ty] == 0)
				continue;
			mp[tx][ty] = 0;
			dfs(tx, ty);
		}
	}
	static void perm(int k, int[] stp) {
		if (k == N) {
			if (check(stp))
				res++;
			return;
		}
		for (int i = 0; i < N; i++) {
			if (i > 0 && a[i-1] == a[i] && !vis[i-1])
				continue;
			if (!vis[i]) {
				vis[i] = true;
				stp[k] = a[i];
				perm(k+1, stp);
				vis[i] = false;
			}
		}
	}
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
		vis = new boolean[N];
		int[] stp = new int[N];
		perm(0, stp);
		System.out.println(res);
    }
}

复杂度分析

• 时间复杂度：$O(n! × R × C)$O(n!×R×C)，
• 空间复杂度：$O(...)$O(...)，