Bo2SS

Bo2SS

6 排列組合與搜索走地圖

—— 遞歸熱身 ——#

HZOJ-240:圖形打印 4#

image

範例輸入

1
2
3
4
-1

範例輸出

X
-
X X
 X
X X
-
X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X
-
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
         X X   X X
          X     X
         X X   X X
            X X
             X
            X X
         X X   X X
          X     X
         X X   X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
-
  • 思路
    • 遞歸
    • func (x, x, n):從點 (x, x) 開始,畫大小為 n 的圖形
      • 邊界:當 n = 1 時,在點 (1, 1),畫 'x'
      • 分解:func (x, x, n) 由 5 個有排列規律的 func (x', x', n - 1) 組成
        • ⭐根據邊長預測 5 個部分的起始點的位置
          • 邊長 L 是首項為 1,公比為 3 的等比數列
          • 以左上角點為基準:其餘 3 個頂點的偏移量是 L / 3 * 2、中心點的偏移量是 L / 3
    • 需要輸出多次,而 n 最大為 7
      • 所以,直接存好 func (1, 1, 7) 的結果,根據輸入 n 輸出即可
  • 代碼
    • 圖片
    • 先存好圖形數組,5 個部分的起始點位置

—— 排列組合 ——#

  • 排列組合三兄弟:指數型、組合、全排列
    • 延伸
      • 【組合問題】對於 1 個數組 num [100],任選 5 個數,輸出和
      • 【全排列問題】對於 1 個數組 num [100],輸出全排列
      • 【組合 + 全排列】n 個數任選 m 個數,再對 m 個數全排列,即 236 + 237 組合練習
        • 先組合,再對得到的組合數進行全排列
      • 【3 兄弟自由組合】
  • 時間複雜度都很高
    • 全排列:O (n!)

HZOJ-235:遞歸實現指數型枚舉#

圖片

範例輸入

3

範例輸出

1
1 2
1 2 3
1 3
2
2 3
3
  • 思路
    • 按字典序排序
    • 遞歸的每一層選一個數字
      • 第 1 層:在 1 ~ n 中選
      • 若某一層選出 i,則下一層:在 i + 1 ~ n 中選。注意:直接 + 1!
    • 舉例:n = 4

第一層:1 2 3 4 中選→1
第二層:2 3 4 中選→2
第三層:3 4 中選→3
第四層:4 中選→4

  • 代碼
    • 第一版:func 函數用2 個參數,便於理解→從幾開始選 + 這是第幾層
    • 圖片
    • 用 num [15] 存前面已經存好的數,最多 10 個數
    • 第二版:func 函數用1 個參數,更有回溯感→從幾開始選【把這是第幾層放到全局裡】
    • 圖片
    • 注意:與版本一不同,這裡的深度 cnt 是從 0 開始,版本一的 deep 是從 1 開始
      • 深度從 1 還是 0 取決於自己,但自己在存值和輸出時要統一

HZOJ-236:遞歸實現組合型枚舉#

圖片

範例輸入

5 3

範例輸出

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
  • 思路
    • 類似上一題 [指數型枚舉],直接修改的話:增加輸出條件,存了 m 個數才輸出
    • 同樣可用 2 個或 3 個參數:多一個輸出條件,存的深度達到 m 才輸出
      • 2 個更有回溯感;3 個更易理解
  • 代碼
    • func 函數用 2 個參數版
    • 圖片
    • 可自己手寫體會
    • 【經測試】實際上變量 cnt 或 left 中的一個可以不需要
      • 不要 left:第 12 行,cnt 可由 m 代替;第 26 行,cnt 可由 m - left 代替;清除其他 cnt
      • 但用 cnt 理解更清晰

HZOJ-237:遞歸實現排列型枚舉#

圖片

範例輸入

3

範例輸出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
  • 思路
    • 全排列
      • 每一層都是 1~n:這一層與上一層沒關係
      • 引入 mark 數組:標記已經選了哪些數了
    • C++ 裡自帶全排列函數 next_permutation、prev_permutation
  • 代碼
    • 圖片
    • 添加標記數組,打標記操作和 cnt 加減操作的配合

—— 深搜 ——#

  • 接上:遞歸👉排列組合👉搜索(深搜)
    • 排列組合其實是深搜的一種
    • 聯想樹的遍歷
    • 往下搜:cnt++;往上回:cnt--
  • ⭐主要解決【連通性】問題
    • 兩個點是否相連,相連的點有哪些、有多少
    • 解決最短路徑問題很費勁,需要遍歷所有路徑,可以找但沒必要

深搜走地圖 —— 基本模板#

  • 圖片
  1. 方向數組:根據目前所在點可以得到下一點的位置,判斷是否可走、到達終點
  2. 存地圖:補 0,可以減少邊界判斷,如果用 vector 需要手動判斷邊界
  3. 遞歸、去重 [或標記數組]、補 0 [或判斷邊界]

代碼

  • 圖片
  • 每次拿到新的點,就以新的點為起點再搜 [遞歸]

  • 走到終點會提前停止搜索,走不到的情況會把所有路徑都枚舉一遍

HZOJ-535:瓷磚#

圖片

範例輸入

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

範例輸出

59
  • 思路
    • 深搜、走到底;廣搜也能做
    • 注意:輸入 h、w 的順序
      • 範例為 9 行 11 列,輸入為 11 9
    • 能走多少個 '.',用一個答案 ans 存,起始為 1
  • 代碼
    • 圖片
    • 不需要返回值,統計全局變量 ans 即可

HZOJ-397:殭屍來襲#

圖片

範例輸入

5 6
0 1 2 3 4 0
1 0 0 0 0 0
2 9 3 0 2 4
0 0 2 0 2 8
1 0 0 0 0 0

範例輸出

4
  • 思路
    • 遍歷,找到一個非 0,波數 + 1,並以其為起點,【深搜】清除和它一波的殭屍
      • 每經過一個非 0,就置為 0,避免之後的重複搜索
    • 再下一波
    • 非 0 值的數值大小在這裡沒有用,只管 0 / 非 0
  • 代碼
    • 圖片
    • 連通性問題,注意去重、輸入地圖為 int 型

HZOJ-536:最大黑色區域#

圖片

範例輸入

5 6
011001
110101
010010
000111
101110

範例輸出

7
  • 思路
    • 上題為有幾片黑色區域,這題為最大的黑色區域有多大
    • 記錄臨時最大值即可
    • 注意
      • 輸入的矩陣是字符,可以一次讀入一行:cin >> &mmap [i][1];
      • 去重
  • 代碼
    • 圖片

HZOJ-396:填塗顏色⭐#

圖片

範例輸入

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

範例輸出

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
  • 思路
    • 只有 0、1
    • 被 1 包住的 0 沒法判斷,但【沒被 1 包住的 0】可以判斷!
      • ❗ 沒被 1 包住的 0 肯定與邊界相連
      • 把沒被包住的 0 改成其他值:3
      • 【輸出只管】遇到 3 輸出 0,遇到 0 輸出 2
    • 如何找沒被 1 包住的 0 呢?
      • ❌方法一:遍歷整個外圈,遇到 0 就深搜
        • 圖片
        • 【麻煩】0 有可能被 1 分割,有多片區域,所以要遍歷整個外圈
      • ⭐方法二:補 0,找和左上角點 [0, 0] 點聯通的 0
        • 圖片
        • 【妙】這些 0 和沒被 1 包住的 0 全是連通的,可以一次搜索處理掉!
        • 注意:必須嚴格判斷邊界
  • 代碼
    • 圖片
    • 注意判斷邊界、輸出判斷

HZOJ-404:01 迷宮簡易版#

圖片

範例輸入

2 3
011
100
2 3

範例輸出

2
  • 思路
    • 深搜,相當於求最大連通域
    • 移動方式為:0→1,1→0。即不相同才能移動
    • ⭐引入標記數組
      • 【去重】該場景使用標記數組更方便,減少判斷次數
    • 【不能補 0】0 在本題有特殊用途,需額外判斷邊界
  • 代碼
    • 圖片
    • 標記數組的引入!
    • 需要判斷邊界,因為搜索條件為不相同時繼續
      • 雖然這裡像是補了 0,其實沒用到

HZOJ-405:01 迷宮⭐#

圖片

範例輸入

2 3 4
011
100
1 1
2 2
1 3
2 3

範例輸出

4
4
2
2
  • 思路
    • 深搜
    • 與上題的區別:詢問次數很多!高達 30000 次
      • 如果用上題方式,每來一個坐標求一次,必超時
    • 👇空間【答案數組】換時間👇
    • 需要額外的數組存每個點的答案:ans [3005][3005]
      • ⭐此外,需要用隊列[方便,棧、數組都行] 存某個連通區域的點集合
      • 只有搜索完這一個連通域才知道它們的答案 [相同的]
  • 代碼
    • 圖片
    • ❗ 答案數組兼任標記數組去重
    • 這裡,補 0 沒有作用,只是習慣從 1 開始讀了
    • 隊列的 size () 其實也是當前的答案 temp
    • 輸出,直接輸出答案數組對應坐標的值即可

—— 廣搜 ——#

  • 同樣可解決【連通性】問題。如HZOJ-396:填塗顏色,思路見上

  • 圖片
  • 除了可以解決【連通性】問題外,還可以解決⭐【最短路徑】問題

    • 從起點到終點最少需要多少步
    • 最先搜到的點一定是最短的,因為是按層來的→層序遍歷

廣搜走地圖 —— 基本模板#

  • 圖片
  1. 方向數組、存地圖
  2. 隊列 [必須]:存遍歷的點,而不需要遞歸;其元素為自定義結構,存坐標、當前步數
  3. 去重 [或標記數組]、補 0 [或判斷邊界]

代碼

  • 圖片
  • 關鍵:入隊出隊、自定義結構體

HZOJ-399:小明吃飯#

圖片

範例輸入

5 6
2.....
###.#.
....#.
..###.
....3.

範例輸出

10
  • 思路
    • 即廣搜走地圖 —— 基本模板
  • 代碼
    • 圖片
    • 去重:改成非可走的字符 '.' 即可,如 0

HZOJ-304:騎士風度的牛#

圖片

範例輸入

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

範例輸出

5
  • 思路
    • 像馬的走法
    • 方向數組變成 8 個
      • [1, 2] 和 [2, 1] 組合各四種
      • 沒有憋腿的情況
    • 注意越界問題:從 1, 1 點存還要判斷邊界,直接從 2, 2 點存
    • 坑:先輸入列數
  • 代碼
    • 圖片
    • 基本模板題,關鍵在方向數組變了

HZOJ-398:馬的遍歷#

圖片

範例輸入

3 3 1 1

範例輸出

0 3 2
3 -1 1
2 1 4
  • 思路
    • 從起點往外搜,仍為 8 個方向
    • 【疑問】
      • 是否是地圖?什麼障礙都沒有,就是一個數組
      • 如何去重呢?同樣利用數組,判斷位置上的值
      • 判斷邊界呢?基於數組,判斷方便
        • 若不判斷,需把所有點右移下移一位考慮,且要把外面 2 圈做成障礙,麻煩!
    • 一個大數組 num [405][405]:既存答案,又去重
      • 【題意】不可達輸出 - 1,起點輸出 0
      • 兩種初始化方式
        • [孬] 初始化為 0:需要兩個特判,一個到不了的點 [0 → -1],起點 [0]
        • 🆗初始化為 - 1:完美
  • 代碼
    • 圖片
    • 題意裡的坐標是 [1, 1] 算起的,但還要判斷邊界,因為馬走法要預留 2 圈,且沒有將邊界設置障礙
    • 用數組 num 代替地圖,還存答案、去重
    • memset -1 是精髓

HZOJ-400:奇怪的象棋遊戲#

圖片

範例輸入

12 16
18 10

範例輸出

8
9
  • 思路
    • 棋盤大小固定為 500 * 500
    • 12 個方向,2 次搜索,一個套路
  • 代碼
    • 注意第 2 次搜索的可能優化,碰見走過的點,直接用當前步數加上 [上一次搜索答案 - 存的步數]
    • 直接看下一題,方法更有意思

HZOJ-401:奇怪的象棋遊戲升級版#

圖片

範例輸入

2
12 16
18 10

範例輸出

8
9
  • 思路
    • 搜索高達 2000 次,上題的思路肯定超時
    • ⭐終點固定,從 [1, 1] 往外走,記錄一個答案數組
      • 這裡從起點到終點和從終點到起點的答案一樣,注意根據題意來
    • 思路反過來後,類似 OJ-398 題了
  • 代碼
    • 圖片
    • 同樣 memset -1,考慮起點步數為 0
    • 本題棋盤足夠大,不需要考慮走不到的情況,走不到一般是棋盤奇小

HZOJ-303:矩陣距離一#

圖片

圖片

範例輸入

3 4
0001
0011
0110

範例輸出

3 2 1 0
2 1 0 0
1 0 0 1
  • 思路
    • 輸入:char!待會判斷邊界可用
    • 這個距離其實就是一個一個走的步數
    • 同上題思路,終點變起點,但有多個起點,且本題有輸入地圖
      • image
      • 從每個起點開始,依次 4 個方向走 1 步,走完就下一位
  • 代碼
    • image
    • 同樣,memset 初始化 num 為 - 1
    • 通過答案數組去重,地圖保持不變
      • 答案數組可以和地圖統一為一個嗎?不行,輸出需要用到答案數組,方便輸出 - 1,也方便理解

HZOJ-305:乳草的入侵#

圖片

範例輸入

4 3 1 1
....
..*.
.**.

範例輸出

4
  • 思路
    • 輸入:行列數調換、起點坐標 (1, 1) 是左下角的格
      • 起點坐標同樣也是反的
      • 把 (1, 1) 點當作 (Y, 1) 點
      • 原則:以我們常用的坐標系為準,調整到我們的坐標系中
    • 8 個方向
    • ⭐新的套路:沒有終點,遍歷完就是結果
      • 終止狀態:隊列為空
      • 如何記錄最遠步數?用一個變量!
  • 代碼
    • 圖片
    • 注意輸入、去重、最遠的步數記錄

HZOJ-529:龍與蟲#

圖片

範例輸入

3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0

範例輸出

1
Impossible!
  • 思路
    • [孬] 直接從起點廣搜;每走一步就判斷:通過方向數組循環 + 1,再一一做判斷,判斷非常多
    • ⭐反轉思維,但又不完全反轉
      • 先從敵人出發,通過方向數組標記所有能被直接幹掉的點,作為【終點集合】
      • 再從起點廣搜,只有當蟲子【移動到】終點集合裡才能幹掉敵人,輸出此時的步數
    • 多組數據,使用標記數組
      • 原地圖不能變,還需要用
      • 開額外的數組做標記:用 1 標記終點、用 2 標記走過的點
      • 對每組數據,重新創建該數組或清空皆可
    • 標記敵人是關鍵
  • 代碼
    • 圖片
    • 圖片
    • 題意:坐標從 [1, 1] 開始
    • 對於【多組輸入】數據,封裝成函數,否則需要用 flag 標志是否結束,因為會有兩層循環
    • 標記數組是局部變量,對於每次輸入數據都是全新的
    • 廣搜或方向數組遍歷的時候別忘記【自己】的情況,因為其判斷不到
    • 不標記起點也沒錯,但是多走一次起點

HZOJ-527:飛躍原野#

圖片

範例輸入

4 4 2
PLLP
PPLP
PPPP
PLLP

範例輸出

5
  • 思路
    • 起點:[1, 1];終點:[m, n]
    • 飛行距離有限,為 D,等同於總能量
    • 【1】去重需要增加一個維度:剩餘能量
      • 因為:數據範圍小 100;且不同剩餘能量對於不同的可能走法,需區分
      • 創建三維數組:點的坐標 x y、剩餘能量
      • 元素值 [標記]:就用 0、1 即可
      • 自定義結構也多一維,記錄此時的剩餘能量
    • 【2】走 or 飛
      • 飛的範圍:2 ~ 剩餘能量,只有 ≥ 2 步的飛才有意義,不然走還省能量
  • 代碼
    • 圖片
    • 【關注】增加剩餘能量維度去重、飛的方式
    • 注意:飛裡面是 break
    • [PS] 在能量足夠的時候,這種暴力枚舉的方式其實會有一些無效的【回飛】的情況,但是也只會在最優的步數裡走出無效的情況。這實際上是由三維去重數組導致的

雖然對某個剩餘能量的坐標去重了,但對於 PPPPP (12345) 這樣的情況,如果能量足夠,會有 1-3-5-3-5-3 這樣的走法

附加知識點#

  • C++ 裡自帶全排列函數 next_permutation、prev_permutation

思考點#

⭐搜索套路:5 步走#

  • 存、起、終、轉、重【詳見下一章:7 搜索綜合問題】

Tips#


課程速記#

載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。