LiaN

是一只废物捏

0%

【题解】DFS

发表于 更新于 分类于 本文字数： 1.1k 阅读时长 ≈ 1 分钟
  • 所有用到DFS的题，从简单到难
  • 栈stack、O(h)、不具有最短性
  • 回溯、剪枝er~

AcW-842. 排列数字 

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
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int a[N];
bool st[N];
//dfs每一个位置 
void dfs(int x){
	if(x>n){
		for(int i=1;i<=n;i++)
			cout<<a[i]<<' ';
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++){
		if(!st[i]){
			st[i]=true;
			a[x]=i;
			dfs(x+1);
			st[i]=false;
		}
	} 
}
int main(){
	cin>>n;
	dfs(1);
}

AcW-843. n-皇后问题

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
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
char g[N][N];
bool row[N],col[N],rd[N],ld[N];
void dfs(int x){
	if(x>n){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)
				cout<<g[i][j];
			cout<<endl;
		}
		cout<<endl;
		return;		
	}
	for(int y=1;y<=n;y++){
		if(!col[y]&&!rd[x+y-1]&&!ld[n+x-y]){
			g[x][y]='Q';
			col[y]=rd[x+y-1]=ld[n+x-y]=true;
			dfs(x+1);
			col[y]=rd[x+y-1]=ld[n+x-y]=false;
			g[x][y]='.';
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) g[i][j]='.';
	dfs(1);
}