DFS練習
- aw842.排列數
- 題目描述
- 思路分析
- 代碼實作
- aw843.N-皇后問題
- 題目描述
- 思路分析
- 代碼實作
aw842.排列數
題目描述
題目鏈接：https://www.acwing.com/problem/content/844/
思路分析
代碼實作
#include<iostream>
using namespace std;
const int N = 10;
int n;
int path[N];//保存序列
bool state[N];//位置是否被用過
void dfs(int u)
{
if(u > n)//數字填完了則輸出
{
for(int i = 1; i <= n; i++)
cout << path[i] << " "; //輸出方案
cout << endl;
}
//空位上可以選擇的數字為1~n
for(int i = 1; i <= n; i++)
{
if(!state[i])//如果i位置沒有被用過
{
path[u] = i;//放入空位
state[i] = true;//陣列被用，記為true
dfs(u + 1);//填寫下一個位置
state[i] = false;//回溯
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
aw843.N-皇后問題
題目描述
題目鏈接：https://www.acwing.com/problem/content/description/845/
思路分析
- 思路一：按行列舉
- 思路二：按元素個數列舉
代碼實作
- 按行搜索
#include<iostream>
using namespace std;
const int N = 20;
int n;
bool col[N],dg[N],udg[N];//col：列 dg：對角線 udg：反對角線
char g[N][N]; //用來存路徑
void dfs(int u)
{
if(u == n) //表示已經搜了n行，則輸出這條路徑
{
for(int i = 0; i < n; i++) puts(g[i]);
puts("");
return;
}
//對n個位置按行搜索
for(int i = 0; i < n; i++)
{
//剪枝：對于不滿足要求的點，不再往下搜索
if(!col[i] && !dg[u + i] && !udg[n - u + i])
{
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n - u + i] = false;//恢復現場
g[u][i] = '.';
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = '.';
dfs(0);
return 0;
}
- 按元素搜索
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; // 因為是一個個搜索，所以加了row
// s表示已經放上去的皇后個數
void dfs(int x, int y, int s)
{
// 處理超出邊界的情況
if (y == n) y = 0, x ++ ;
if (x == n) // x==n說明已經列舉完n^2個位置了
{
if (s == n) // s==n說明成功放上去了n個皇后
{
//輸出這組解
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
}
return;
}
// 分支1：放皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
// 分支2：不放皇后
dfs(x, y + 1, s);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0, 0, 0);
return 0;
}
- 思路一的效率更高一些
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286704.html
標籤：其他