一道Dfs+Dfs的好题目~

[TOC]

题目链接：·【蓝桥】·剪邮票
涉及到有图片就不贴题目了

题目分析
3*4的矩阵，随意选取5个方格，要求方格是相连着的

算法分析

1. 很难在二维数组中枚举，因此可以枚举一维数组a[12]，再将其转为二维的
   所以第一层Dfs，全排列数组a[]={0,0,0,0,0,0,0,1,1,1,1,1}

2. 数组a[] 中1表示选取的方格，那么接下来只需将全排列的a[]升为二维，判断是否相连即可

   //一维升二维
   for(int i = 0; i < 3; ++i){
   	for(int j = 0; j < 4; ++j){
   		if(a[i*4+j] == 1)
   			g[i][j] = 1;
   		else
   			g[i][j] = 0;
   	}
   }

3. 判断矩阵中相连方格的组数，又是一层经典的Dfs，这里要求相连的方格仅1组

   //第二层Dfs判断是否相连
   int dx[] = {0, 1, 0, -1};
   int dy[] = {1, 0, -1, 0};
   int cnt = 0;
   void dfs(int g[3][4], int i, int j){
   	g[i][j] = 0;
   	for(int k = 0; k < 4; ++k){
   		int tx = i + dx[k];
   		int ty = j + dy[k];
   		if(tx>=0 && ty>=0 && tx<3 && ty<4 && g[tx][ty]==1)
   			dfs(g, tx, ty);
   	}
   }
   //check()中内容
   bool check(){
   	int g[3][4];
   	for(int i = 0; i < 3; ++i){
   		for(int j = 0; j < 4; ++j){
   			if(a[i*4+j] == 1)
   				g[i][j] = 1;
   			else
   				g[i][j] = 0;
   		}
   	}
   	int cnt = 0;
   	for(int i = 0; i < 3; ++i){
   		for(int j = 0; j < 4; ++j){
   			if(g[i][j] == 1){
   				dfs(g, i, j);
   				cnt++;
   			}
   		}
   	}
   	return cnt == 1;
   }

***注意：数组a[]的全排列要求去重，我的另一篇博客专门有全排列去重
总结一下有三种去重写法：

1. C++的next_permutation
2. 基于新数组的全排列
3. 原数组上进行的全排列 

1、C++的next_permutation

——————————————完整代码1————————————————

#include <iostream>
#include <algorithm>

using namespace std;

int a[] = {0,0,0,0,0,0,0,1,1,1,1,1};
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0}; 
int ans = 0;
void dfs(int g[3][4], int i, int j){
	g[i][j] = 0;
	for(int k = 0; k < 4; ++k){
		int tx = i + dx[k];
		int ty = j + dy[k];
		if(tx>=0 && ty>=0 && tx<3 && ty<4 && g[tx][ty]==1)
			dfs(g, tx, ty);
	}
}
bool check(){
	int g[3][4];
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 4; ++j){
			if(a[i*4+j] == 1)
				g[i][j] = 1;
			else
				g[i][j] = 0;
		}
	}
	int cnt = 0;
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 4; ++j){
			if(g[i][j] == 1){
				dfs(g, i, j);
				cnt++;
			}
		}
	}
	return cnt == 1;
}
void solve(int k){
	do{
		if(check())
			ans++;
	}while(next_permutation(a, a+12));
}
int main(){
	solve(0);
	cout << ans << endl;
	return 0;
}

2、基于新数组的全排列

——————————————完整代码2————————————————

//仅solve()与上面代码不同
int v[12], b[12];
void solve(int k){
	if(k == 12){
		if(check()){
			ans++;
		}
		return;
	}
	for(int i = 0; i < 12; ++i){
		if(i>0 && a[i-1]==a[i] && !v[i-1])
			continue;
		if(!v[i]){
			v[i] = 1;
			b[k] = a[i];
			solve(k+1);
			v[i] = 0;
		}
	}
}

3、原数组上进行的全排列

——————————————完整代码3————————————————

//涉及到set去重代码量就更大了
#include <iostream>
#include <set>

using namespace std;

int a[] = {0,0,0,0,0,0,0,1,1,1,1,1};
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0}; 
int ans = 0, tmp = 0;
set<string> s;
void to_string(string &str){
	for(int i = 0; i < 12; ++i){
		str.insert(str.end(), a[i]+'0');
	}
}
bool isExist(){
	string str;
	to_string(str);
	if(s.find(str) == s.end()){
		s.insert(str);
		return false;
	}
	return true;
}
void dfs(int g[3][4], int i, int j){
	g[i][j] = 0;
	for(int k = 0; k < 4; ++k){
		int tx = i + dx[k];
		int ty = j + dy[k];
		if(tx>=0 && ty>=0 && tx<3 && ty<4 && g[tx][ty]==1)
			dfs(g, tx, ty);
	}
}
bool check(){
	int g[3][4];
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 4; ++j){
			if(a[i*4+j] == 1)
				g[i][j] = 1;
			else
				g[i][j] = 0;
		}
	}
	int cnt = 0;
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 4; ++j){
			if(g[i][j] == 1){
				dfs(g, i, j);
				cnt++;
			}
		}
	}
	return cnt == 1;
}
void solve(int k){
	if(k == 12){
		if(!isExist() && check()){
			ans++;
		}
		return;
	}
	for(int i = k; i < 12; ++i){
		{
			int t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
		solve(k+1);
		{
			int t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
}
int main(){
	solve(0);
	cout << ans << endl;
	return 0;
}