最近有點忙，沒來得及寫博客，讓大家久等啦，
上節課蒟蒻君給大家講了dfs如何解決列舉型別的題，這節課咱們將會講到它的另一種用途——圖論上的用途（針對圖和樹的演算法），
大家看到標題肯定會想：什么叫計算思維？
計算思維就是將不好表示的東西用數來表示，比如以下幾道題：
鋪墊1
- 題目
有四位同學其中對一位多次扶老奶奶過馬路 （老奶奶們很善良，不會碰瓷） ，不留名，表揚信下來后，老師問是哪位同學做的好事，
- A說：不是我，
- B說：是C，
- C說：是D，
- D說：他胡說，
經過老奶奶們的確認，知道了三個同學中有一個說的是假話，其余都是真話，現在請你根據以上資訊，寫出程式找到做好事的人， - 分析
我們如果不從數學對角度去考慮 （因為數學的太簡單了 ） ，要完成本任務，我們首先要將這四個人說的自然語言改變成計算機能看懂的可計算的式子，
在本題里，這個式子用的就是所謂的“布爾代數”，
我們先假設每個人是做好事的那位同學，并且帶入，判斷是否矛盾即可，
- 關系運算式
先假設做好事的人為thisman，
- 代碼
#include <bits/stdc++.h>
using namespace std;
int main() {
for (int k = 0; k < 4; ++k) {
char thisman = 'A' + k;
// 如果3句話為真，則輸出當前可能性所假定的人為做好事者
if ((thisman != 'A') + (thisman == 'C') + (thisman == 'D') + (thisman != 'D') == 3) {
cout << thisman << "做了好事\n";
return 0;
}
}
cout << "無人做了好事\n";
return 0;
}
鋪墊2
- 題目
現在農場里有編號為0，1，2，3，4的五袋飼料，和A、B、C、D、E五只小豬豬，請你幫助農場主寫一個程式，輸出使得所有豬都能吃到喜歡的飼料的方案，
假設五只豬喜歡吃的飼料如下表：
- 解題思路
step1:吃食興趣用一個二維陣列描述，
const int like[5][5] = {{0, 0, 1, 1, 0},
{1, 1, 0, 0, 1},
{0, 1, 1, 0, 1},
{0, 0, 0, 1, 0},
{0, 1, 0, 0, 1}};
step2:飼料狀態用一個一維陣列描述，
int assigned[5];
陣列元素存盤的是分配到下標對應飼料的小豬豬編號，若assigned[book_id] == -1 則表示book_id這袋飼料沒有分配，
注意：陣列下標是的編號，
開始，所有飼料都未分配，我們要做出以下的預處理：
memset(assigned, -1, sizeof(assigned));
step3:遞回（與或圖），
- 代碼
#include <bits/stdc++.h>
using namespace std;
const int like[5][5] = {{0, 0, 1, 1, 0},
{1, 1, 0, 0, 1},
{0, 1, 1, 0, 1},
{0, 0, 0, 1, 0},
{0, 1, 0, 0, 1}};
int sum; // 總方案數
int assigned[5];
void Try(int pig) { // 也就是所謂的dfs函式
// 遞回終止條件：所有豬都分配到了合適的飼料
if (pig == 5) {
cout << "第" << ++sum << "個方案：";
for (int i = 0; i < 5; ++i) {
cout << assigned[i] << ' ';
}
cout << '\n';
return ;
}
// 為每袋飼料找到合適的豬
for (int feed = 0; feed < 5; ++feed) {
// 判斷是否滿足分飼料的條件
if (like[pig][feed] != 1 || assigned[feed] != -1) {
continue;
}
// 記錄這袋飼料的分配情況
assigned[feed] = pig;
// 為下一只豬找到合適的飼料
Try(pig + 1);
// 回溯，嘗試另一袋飼料
assigned[feed] = -1;
}
}
int main() {
memset(assigned, -1, sizeof(assigned));
Try(0); // 從編號為0的豬開始尋找方案
return 0;
}
- 拓展延伸：是否可以不使用回溯
#include <bits/stdc++.h>
using namespace std;
const int like[5][5] = {{0, 0, 1, 1, 0},
{1, 1, 0, 0, 1},
{0, 1, 1, 0, 1},
{0, 0, 0, 1, 0},
{0, 1, 0, 0, 1}};
int sum; // 總方案數
void Try(int pig, int assigned[]) {
// 遞回終止條件：所有豬都分配到了合適的飼料
if (pig == 5) {
cout << "第" << ++sum << "個方案：";
for (int i = 0; i < 5; ++i) {
cout << assigned[i] << ' ';
}
cout << '\n';
return ;
}
// 為每袋飼料找到合適的豬
for (int feed = 0; feed < 5; ++feed) {
// 判斷是否滿足分飼料的條件
if (like[pig][feed] != 1 || assigned[feed] != -1) {
continue;
}
// 記錄這袋飼料的分配情況
int nxt_assigned[5];
for (int i = 0; i < 5; ++i) {
nxt_assigned[i] = assigned[i];
}
nxt_assigned[feed] = pig;
// 為下一位豬豬找飼料
Try(pig + 1, nxt_assigned);
}
}
int main() {
int assigned[5]; // 為了不與Try函式的引數重名，在main函式內部定義
memset(assigned, -1, sizeof(assigned));
Try(0, assigned); // 從編號為0的豬開始尋找方案
return 0;
}
無關緊要
想必大家已經掌握“計算思維”的精髓啦，我們看看如何把這個思維用到dfs中~
知識概述
dfs里有一個經典問題，叫“迷宮問題”，在迷宮里，要做出很多操作，但無論在什么樣的迷宮中，目前的位置都是必須要記錄噠！
題目中的人物可以在迷宮里像很多方向走（最常見的就是上下左右），我們要記錄的就是目前的坐標，而所謂的方向陣列就是位置改變的原則，
比如：
const int dir_arr[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // 上下左右
例題1：八皇后問題
在一個8*8的棋盤里，放置8個皇后，使得兩兩互不攻擊，
- 思路1：for回圈列舉
#include <bits/stdc++.h>
using namespace std;
#define f(n) for (q[(n) = 1]; q[(n)] <= 8; ++q[(n)])
bool is_safe(int q[]) {
......
}
int main() {
int q[9];
int sum = 0;
f(1) f(2) f(3) f(4) f(5) f(6) f(7) f(8)
if (is_safe(q)) {
cout << "第" << ++sum << "種方法：";
for (int i = 1; i <= 8; ++i) {
cout << q[i] << ' ';
}
cout << '\n';
}
return 0;
}
太暴力啦！！！
明顯，這個演算法的時間復雜度確實有點太高了，有沒有其他方法呢？
- 思路2：列舉+遞回 = 深度優先搜索（與或圖）
#include <bits/stdc++.h>
using namespace std;
const int N = 9, M = 17;
int sum; // 方案數
int Q[N]; // 8個皇后所占用的行號
bool S[N]; // 當前行是否安全
bool L[M]; // 右上到左下的對角線是否安全
bool R[M]; // 左上到右下的對角線是否安全
void dfs(int col) {
// 遞回終止條件：所有列都有皇后了
if (col == N) {
cout << "第" << ++sum << "種方案：";
for (int i = 1; i <= 8; ++i) {
cout << Q[i] << ' ';
}
cout << '\n';
return ;
}
// 嘗試當前列8行的位置
for (int row = 1; row < N; ++row) {
// 判斷是否安全
if (!S[row] || !L[col - row + N] || !R[col + row]) {
continue;
}
// 記錄當前行號
Q[col] = row;
// 修改是否安全的標記
S[row] = false;
L[col - row + N] = false;
R[col + row] = false;
// 繼續嘗試下一列
dfs(col + 1);
// 回溯
S[row] = true;
L[col - row + N] = true;
R[col + row] = true;
}
}
int main() {
for (int i = 0; i < N; ++i) {
S[i] = true;
}
for (int i = 0; i < M; ++i) {
L[i] = R[i] = true;
}
// 從第一行開始判斷
dfs(1);
return 0;
}
- 拓展延伸：能否不使用回溯
struct state {
int Q[N]; // 8個皇后所占用的行號
bool S[N]; // 當前行是否安全
bool L[M]; // 右上到左下的對角線是否安全
bool R[M]; // 左上到右下的對角線是否安全
} s;
void dfs(int col, state S) {
// 遞回終止條件：所有列都有皇后了
if (col == N) {
cout << "第" << ++sum << "種方案：";
for (int i = 1; i <= 8; ++i) {
cout << s.Q[i] << ' ';
}
cout << '\n';
return ;
}
// 嘗試當前列8行的位置
for (int row = 1; row < N; ++row) {
// 判斷是否安全
if (!s.S[row] || !s.L[col - row + N] || !s.R[col + row]) {
continue;
}
// 記錄當前行號
state nxt = s;
nxt.Q[col] = row;
// 修改是否安全的標記
nxt.S[row] = false;
nxt.L[col - row + N] = false;
nxt.R[col + row] = false;
// 繼續嘗試下一列
dfs(col + 1, nxt);
}
}
例題2：過河卒
- 題目
- 思路1：暴力搜索
先算出所有“馬的控制點”，然后用深度優先搜索嘗試每一條不途徑這些點的路徑，
代碼
#include <bits/stdc++.h>
using namespace std;
const int dir_zu[2][2] = {{0, 1}, {1, 0}}; // 卒的方向陣列，只能向右和向下走
const int dir_ma[2][9] = {{0, -2, -1, 1, 2, 2, 1, -1, -2},
{0, 1, 2, 2, 1, -1, -2, -2, -1}}; // 馬的方向陣列
int n, m; // B點坐標
int x, y; // 馬的坐標
int sum; // 總方案數
bool is_danger[30][30]; // (i, j)是否危險，false代表安全
inline bool judge_in(int x, int y) { // 判斷點(x, y)是否在棋盤里
return x >= 0 && x <= n && y >= 0 && y <= m;
}
void init() { // 初始化
is_danger[x][y] = true; // 馬現在的點肯定是馬的控制點
for (int i = 0; i < 9; ++i) {
int pre_x = x + dir_ma[0][i]; // 目前點的x坐標
int pre_y = y + dir_ma[1][i];
if (judge_in(pre_x, pre_y)) { // 判斷是否在棋盤里
is_danger[pre_x][pre_y] = true; // 標記為不安全
}
}
}
void dfs(int x, int y) {
// 遞回終止條件：卒已到達B點（坐標相等）
if (x == n && y == m) {
++sum;
return ;
}
// 嘗試每一種方向
for (int i = 0; i < 2; ++i) {
int nxt_x = x + dir_zu[i][0]; // 下一個點的x坐標
int nxt_y = y + dir_zu[i][1]; // 下一個點的y坐標
if (!judge_in(nxt_x, nxt_y) || is_danger[nxt_x][nxt_y]) { // 判斷是否可以繼續走
continue;
}
dfs(nxt_x, nxt_y); // 可以走就繼續走
}
}
int main() {
cin >> n >> m;
cin >> x >> y;
init();
dfs(0, 0);
cout << sum << '\n';
return 0;
}
但是，在luogu上，這個代碼的最后三個資料都TLE啦！
所以，我們要想一個新的思路…
這個思路在以后蒟蒻君給大家講dp（動態規劃）的時候會講到，現在就是讓大家熟悉以下方向陣列的使用，
例題3：幻想迷宮
- 題目
在這里可憐喵星人一秒鐘，一秒鐘后讓我們開始想題… - 分析程序
這道題明顯是用搜索的（因為蒟蒻君講的是搜索），題目里的迷宮很容易讓人想到dfs，
顯然，我們可以把輸入的一個迷宮變成九個迷宮，判斷從起點(x, y)能否走到(x + n, y)，(x - n, y)，(x, y + m)或(x, y - m)，
但是大家會發現，這樣的空間復雜度是很大噠，明顯會MLE，
所以我們直接對迷宮去mod就好啦，
但是，如果走到過一個點又走到了這個點，那是可以走∞遠的，
這里又出現了一大大大大大大堆問題，
想到這蒟蒻君也懵(′?ω?`)了…
參考網上大佬的題解后發現還有一個巧妙的方法…
我們記錄取模的橫縱坐標x, y，同時記錄沒有取模的坐標X, Y
當第一次走這個迷宮的時候，x, y和X, Y肯定是相等的，
所以只要走到的一個點的x, y和X, Y不相等，那這個點一定是被走了第二遍， - 代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 1505;
const int dir_arr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 方向陣列
int n, m;
int st_x, st_y; // 起點坐標
int vis[N][N][3];
bool flag, a[N][N]; // a[i][j]表示(i, j)是否可走，0表示可以
void dfs(int x, int y, int X, int Y) {
if (flag) {
return ;
}
// 具體含義見分析程序
if (vis[x][y][0] && (vis[x][y][1] != X || vis[x][y][2] != Y)) {
flag = true;
return;
}
vis[x][y][0] = 1;
vis[x][y][1] = X;
vis[x][y][2] = Y;
for (int i = 0; i < 4; ++i) {
int nxt_x = (x + dir_arr[i][0] + n) % n; // 不要忘記每輪的mod
int nxt_y = (y + dir_arr[i][1] + m) % m;
int nxt_X = X + dir_arr[i][0];
int nxt_Y = Y + dir_arr[i][1];
if (!a[nxt_x][nxt_y]) {
if (vis[nxt_x][nxt_y][1] != nxt_X ||
vis[nxt_x][nxt_y][2] != nxt_Y ||
!vis[nxt_x][nxt_y][0]) {
dfs(nxt_x, nxt_y, nxt_X, nxt_Y);
}
}
}
}
int main() {
while (cin >> n >> m) {
// 不要忘記每輪初始化
flag = false; // flag表示每輪答案
memset(a, false, sizeof(a));
memset(vis, false, sizeof(vis));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
char ch;
cin >> ch;
if (ch == '#') { // 不能走到墻上
a[i][j] = 1;
}
if (ch == 'S') { // 記錄起點坐標
st_x = i;
st_y = j;
}
}
}
// 從起點開始嘗試
dfs(st_x, st_y, st_x, st_y); // st_x和st_y取不取mod都是本身
if (flag == true) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
今天的講解就到這里，希望大家看完有所識訓~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/261008.html
標籤：其他