0830-C05DFS

1、排列组合

#if 0 

4
n的全排列: 计算n的阶乘 
排列: 与顺序有关 	Arrangement (Permutation)
组合: 与顺序无关 	Combination 
	
计算方法:
(1)排列数: 
A(n, m) 从n开始以阶乘方式递减往后乘,乘的数字个数为 m个 
A(6, 3) = 6*5*4 
C(6, 3) = 120/6 = 20

(2)组合数 
C(n, m) = A(n, m)/(m!) 

C(7, 4) = A(7, 4)/4! = 35 

(3)性质:
C(n, m) = C(n, n-m);
A(n, n) = n!
 
C(10, 7) = 120 = C(10, 3)
# endif


#include <bits/stdc++.h>
using namespace std;

int main(){
	int n = 3;
	for (int i=1; i<=3; i++){
		for (int j=1; j<=3; j++){
			for (int k=1; k<=3; k++){
				if (i==j || j==k || i== k) continue; 
				printf("%5d%5d%5d\n", i, j, k);
			}
		}
	} 

	return 0;
}

2、全排列问题

/*
DFS
depth first search
深度优先搜索 
*/
#include <bits/stdc++.h>
using namespace std;

int a[105], n; 
bool vis[105];	//标记数组, 标记数字有没有没被使用过 

//function: 往step上放数字 每一层 
void dfs(int step){
	if (step > n){
		for (int i=1; i<=n; i++) cout << setw(5) << a[i];
		cout << endl; 
		return ;
	} 
	for(int i=1; i<=n; i++){
		if (vis[i] == 1) continue; 
		a[step] = i;	//放数字
			
		vis[i] = true;	//标记数字 
		dfs(step + 1);	//放下一个位置
		vis[i] = false;	//取消数字标记 	回溯 
	}
} 

int main(){
	cin >> n;
	dfs(1); 

	return 0;
}

3、自然数的拆分

#include <bits/stdc++.h>
using namespace std;

int n, a[105] = {1};  

//将数字num拆分, step表示位置
void dfs(int num, int step){
	if (num==0 && step > 2){
		for(int i=1; i<step; i++) {
			cout<<a[i];
			if (i!=step-1) cout<<'+';
		}
		cout << endl; 
		return ;
	}
	
	for (int i=a[step-1]; i<=num; i++){
		a[step] = i;
		dfs(num-i, step+1);
		
	}
} 

int main(){
	cin >> n;
	dfs(n, 1);

	return 0;
}

/*
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
*/

4、迷宫问题（template）

/*
*/
#include <bits/stdc++.h>
using namespace std;

bool vis[105][105];		//标记数组 
char mp[105][105];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};	//方向数组 
int n;  
int sx, sy, fx, fy; 

void dfs(int x, int y){
	vis[x][y] = 1;	//标记 
	if (x==fx && y == fy){
		cout << "yes";
		exit(0); 
	} 
	for (int i=0; i<4; i++){
		int nx = x + dir[i][0];	// x的拓展 
		int ny = y + dir[i][1];	// y的拓展 
		if (vis[nx][ny] == 1 || mp[nx][ny]=='#') continue;
		dfs(nx, ny);
	} 
} 

int main(){
	memset(mp, '#', sizeof mp); 
	cin >> n;
	for (int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cin >>mp[i][j];
		}
	} 
	cin>>sx>>sy>>fx>>fy;
	sx++,sy++,fx++,fy++;
	if (mp[sx][sy]=='#' || mp[fx][fy]=='#') {
		cout << "no";
		return 0; 
	}
	
	dfs(sx, sy);
	cout << "no";
	
	return 0;
}