DFS 给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include <bits/stdc++.h>
using namespace std;
const int N = 20 ;
int n;
int m[ N] ;
bool st[ N] ;
void dfs ( int s) {
if ( s == n) {
for ( int i = 0 ; i < n; i ++ )
cout << m[ i] << ' ' ;
cout << endl;
return ;
}
for ( int i = 1 ; i <= n; i ++ ) {
if ( ! st[ i] ) {
st[ i] = 1 ;
m[ s] = i;
dfs ( s + 1 ) ;
st[ i] = 0 ;
}
}
return ;
}
int main ( ) {
cin >> n;
dfs ( 0 ) ;
return 0 ;
}
n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，
即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数n。
输出格式
每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。
其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
#include <bits/stdc++.h>
using namespace std;
const int N = 20 ;
char c[ N] [ N] ;
int n;
bool col[ N] , dg[ N] , udg[ N] ;
void dfs ( int x) {
if ( x == n) {
for ( int i = 0 ; i < n; i ++ )
puts ( c[ i] ) ;
cout << endl;
return ;
}
for ( int y = 0 ; y < n; y ++ ) {
if ( ! col[ y] && ! dg[ n + y - x] && ! udg[ x + y] ) {
col[ y] = dg[ n + y - x] = udg[ x + y] = 1 ;
c[ x] [ y] = 'Q' ;
dfs ( x + 1 ) ;
col[ y] = dg[ n + y - x] = udg[ x + y] = 0 ;
c[ x] [ y] = '.' ;
}
}
return ;
}
int main ( ) {
cin >> n;
for ( int i = 0 ; i < n; i ++ )
for ( int j = 0 ; j < n; j ++ )
c[ i] [ j] = '.' ;
dfs ( 0 ) ;
return 0 ;
}
AcWing 844. 走迷宫 (超级不顺利) BFS禁止套娃! BFS要开栈 给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。
最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。
数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。
输入格式
第一行包含两个整数n和m。
接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8
#include <bits/stdc++.h>
using namespace std;
const int N = 110 ;
typedef pair< int , int > P;
int m, n;
int g[ N] [ N] , d[ N] [ N] ;
P q[ N * N] ;
int bfs ( ) {
int hh = 0 , tt = 0 ;
q[ 0 ] = { 0 , 0 } ;
memset ( d, - 1 , sizeof d) ;
d[ 0 ] [ 0 ] = 0 ;
int dy[ 4 ] = { - 1 , 1 , 0 , 0 } , dx[ 4 ] = { 0 , 0 , - 1 , 1 } ;
while ( hh <= tt) {
auto t = q[ hh ++ ] ;
for ( int i = 0 ; i < 4 ; i ++ ) {
int x = t. first + dx[ i] , y = t. second + dy[ i] ;
if ( x >= 0 && x < n && y >= 0 && y < m && g[ x] [ y] == 0 && d[ x] [ y] == - 1 ) {
d[ x] [ y] = d[ t. first] [ t. second] + 1 ;
q[ ++ tt] = { x, y} ;
}
}
}
return d[ n - 1 ] [ m - 1 ] ;
}
int main ( ) {
cin >> n >> m;
for ( int i = 0 ; i < n; i ++ )
for ( int j = 0 ; j < m; j ++ )
cin >> g[ i] [ j] ;
cout << bfs ( ) << endl;
return 0 ;
}