6 Combinations and Permutations in Map Navigation

——Recursion Warm-up——#

HZOJ-240: Graphic Printing 4#

Sample Input

Sample Output

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
-

Idea
- Recursion
- func(x, x, n): Start from point (x, x) and draw a shape of size n
  - Boundary: When n = 1, draw 'x' at point (1, 1)
  - Decomposition: func(x, x, n) consists of 5 func(x', x', n - 1) with a regular arrangement
    - ⭐ Predict the starting positions of the 5 parts based on the side length
      - The side length L is a geometric sequence with the first term 1 and a common ratio of 3
      - Using the top-left corner as a reference: the offsets of the other 3 vertices are L / 3 * 2, and the offset of the center point is L / 3
- Need to output multiple times, with n up to 7
  - So, store the result of func(1, 1, 7) directly and output according to the input n
Code
- First, store the shape array, the starting positions of the 5 parts

——Combinations——#

The three brothers of combinations: Exponential, Combination, Permutation
- Extension
  - [Combination Problem] For an array num[100], select any 5 numbers and output the sum
  - [Permutation Problem] For an array num[100], output all permutations
  - [Combination + Permutation] Select m numbers from n numbers, then permute the m numbers, i.e., practice combinations 236 + 237
    - First combine, then permute the obtained combinations
  - [3 Brothers Free Combination]
The time complexity is very high
- Permutation: O(n!)

HZOJ-235: Recursive Implementation of Exponential Enumeration#

Sample Input

Sample Output

Idea
- Sort in lexicographical order
- In each layer of recursion, select a number
  - First layer: select from 1 to n
  - If i is selected in a layer, then in the next layer: select from i + 1 to n. Note: directly +1!
- Example: n = 4

First layer: select from 1 2 3 4 → 1
Second layer: select from 2 3 4 → 2
Third layer: select from 3 4 → 3
Fourth layer: select from 4 → 4

Code
- First Version: func function uses 2 parameters for better understanding → start from which number + which layer it is
- Use num[15] to store previously stored numbers, up to 10 numbers
- Second Version: func function uses 1 parameter, more backtracking feel → start from which number [put the current layer in global]
- Note: Unlike version one, the depth cnt starts from 0, while version one's deep starts from 1
  - Depth starting from 1 or 0 depends on oneself, but one must be consistent when storing values and outputting

HZOJ-236: Recursive Implementation of Combination Enumeration#

Sample Input

5 3

Sample Output

Idea
- Similar to the previous problem [Exponential Enumeration], directly modify: add output condition, output only when m numbers are stored
- Also can use 2 or 3 parameters: add an output condition, output when the depth reaches m
  - 2 parameters feel more backtracking; 3 parameters are easier to understand
Code
- func function uses 2 parameter version
- You can write it yourself to experience
- [Tested] In fact, one of the variables cnt or left can be omitted
  - Without left: in line 12, cnt can be replaced by m; in line 26, cnt can be replaced by m - left; clear other cnt
  - But using cnt is clearer for understanding

HZOJ-237: Recursive Implementation of Permutation Enumeration#

Sample Input

Sample Output

Idea
- Full permutation
  - Each layer is 1~n: this layer is unrelated to the previous layer
  - Introduce mark array: mark which numbers have been selected
- C++ has built-in full permutation functions next_permutation, prev_permutation
  - Reference Full permutation function in STL
  - But actually not very useful, implementing it oneself is more flexible
Code
- Add mark array, mark operation and cnt increment/decrement operations coordination

——Depth Search——#

Continuing: Recursion 👉 Permutation and Combination 👉 Search (Depth Search)
- Permutation and combination are actually a type of depth search
- Relate to tree traversal
- Search down: cnt++; backtrack: cnt--
⭐ Mainly solve the [Connectivity] problem
- Whether two points are connected, which points are connected, and how many there are
- Solving the shortest path problem is very tedious, requiring traversal of all paths, which can be found but is unnecessary

Depth Search Map Navigation——Basic Template#

Direction array: Based on the current point, determine the next point's position, check if it can be traversed, and if it reaches the endpoint
Store the map: fill with 0, which can reduce boundary checks; if using vector, manual boundary checks are needed
Recursion, deduplication [or mark array], fill with 0 [or boundary checks]

Code

Each time a new point is obtained, start searching again from the new point [recursion]
Reaching the endpoint will stop the search early; unreachable cases will enumerate all paths

HZOJ-535: Tiles#

Sample Input

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

Sample Output

Idea
- Depth search, go to the end; breadth search can also be done
- Note: Input order of h and w
  - Sample has 9 rows and 11 columns, input is 11 9
- How many '.' can be traversed, use a variable ans to store, starting from 1
Code
- No return value is needed; just count the global variable ans

HZOJ-397: Zombie Attack#

Sample Input

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

Sample Output

Idea
- Traverse, find a non-zero, increment wave count, and use it as the starting point to [depth search] clear zombies in the same wave
  - Each time a non-zero is passed, set it to 0 to avoid repeated searches later
- Next wave
- The value of non-zero is not useful here, just care about 0/non-zero
Code
- Connectivity problem, pay attention to deduplication, input map as int type

HZOJ-536: Largest Black Area#

Sample Input

Sample Output

Idea
- The previous problem was how many black areas there are; this problem is how large the largest black area is
- Just record the temporary maximum value
- Note
  - The input matrix is characters, can read a line at a time: cin >> &mmap[i][1];
  - Deduplication
Code

HZOJ-396: Fill Color ⭐#

Sample Input

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

Sample Output

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

Idea
- Only 0 and 1
- 0s surrounded by 1s cannot be judged, but [0s not surrounded by 1s] can be judged!
  - ❗ 0s not surrounded by 1s must be connected to the boundary
  - Change the 0s not surrounded by 1s to another value: 3
  - [Output only cares about] output 0 when encountering 3, output 2 when encountering 0
- How to find 0s not surrounded by 1s?
  - ❌ Method 1: Traverse the entire outer circle, and perform depth search when encountering 0
    - 【Troublesome】0s may be divided by 1, leading to multiple areas, so the entire outer circle needs to be traversed
  - ⭐ Method 2: Fill with 0, find 0s connected to the top-left point [0, 0]
    - 【Clever】These 0s and the 0s not surrounded by 1s are all connected, and can be processed in one search!
    - Note: Must strictly check boundaries
Code
- Pay attention to boundary checks and output checks

HZOJ-404: 01 Maze Simple Version#

Sample Input

Sample Output

Idea
- Depth search, equivalent to finding the maximum connected area
- Movement method: 0→1, 1→0. That is, only different can move
- ⭐ Introduce mark array
  - [Deduplication] This scenario uses a mark array for convenience, reducing the number of checks
- [Cannot fill with 0] 0 has a special purpose in this problem, requiring additional boundary checks
Code
- Introduction of mark array!
- Need to check boundaries because the search condition is to continue if they are different
  - Although it seems like filling with 0 here, it is actually not used

HZOJ-405: 01 Maze ⭐#

Sample Input

Sample Output

Idea
- Depth search
- The difference from the previous problem: many queries! Up to 30,000 times
  - If using the previous method, querying once for each coordinate will definitely time out
- 👇 Space [Answer Array] trades time 👇
- Need an extra array to store the answer for each point: ans[3005][3005]
  - ⭐ Additionally, need to use a queue [convenient, stack, array are all fine] to store a collection of points in a connected area
  - Only after searching this connected area can we know their answers [the same]
Code
- ❗ The answer array also serves as the mark array for deduplication
- Here, filling with 0 has no effect; it's just a habit to read from 1
- The size of the queue() is actually the current answer temp
- Output, directly output the value corresponding to the answer array for the coordinates

——Breadth Search——#

Can also solve the [Connectivity] problem. See HZOJ-396: Fill Color, see the above idea
In addition to solving the [Connectivity] problem, it can also solve ⭐ [Shortest Path] problem
- How many steps are needed from the starting point to the endpoint
- The first point found must be the shortest because it comes layer by layer → Level Order Traversal

Breadth Search Map Navigation——Basic Template#

Direction array, store the map
Queue [must]: store the points being traversed, without needing recursion; its elements are a custom structure, storing coordinates and current step count
Deduplication [or mark array], fill with 0 [or boundary checks]

Code

Key: enqueue and dequeue, custom structure

HZOJ-399: Xiaoming Eats#

Sample Input

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

Sample Output

Idea
- This is the basic template for breadth search map navigation
Code
- Deduplication: change to a non-traversable character '.' like 0

HZOJ-304: Knight's Grace#

Sample Input

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

Sample Output

Idea
- Like the knight's moves
- The direction array becomes 8
  - [1, 2] and [2, 1] combinations each have four types
  - No leg entrapment situation
- Note the boundary issue: store from point 1, 1 and check boundaries; directly store from point 2, 2
- Pitfall: input column count first
Code
- Basic template problem, key is that the direction array has changed

HZOJ-398: Knight's Traversal#

Sample Input

3 3 1 1

Sample Output

0 3 2
3 -1 1
2 1 4

Idea
- Search outward from the starting point, still 8 directions
- [Question]
  - Is it a map? There are no obstacles, just an array
  - How to deduplicate? Use an array to check the value at the position
  - How to check boundaries? Based on the array, checking is convenient
    - If not checked, all points would need to be shifted down and right, and the outer two circles would need to be made obstacles, which is troublesome!
- A large array num[405][405]: stores both answers and deduplication
  - [Problem statement] Unreachable outputs -1, starting point outputs 0
  - Two initialization methods
    - [Poor] Initialize to 0: requires two special cases, one unreachable point [0 → -1], starting point [0]
    - 🆗 Initialize to -1: perfect
Code
- The coordinates in the problem statement start from [1, 1], but boundary checks are still needed because the knight's moves need to leave two circles, and the boundary is not set as an obstacle
- Use array num to replace the map, also storing answers and deduplication
- memset -1 is the essence

HZOJ-400: Strange Chess Game#

Sample Input

12 16
18 10

Sample Output

8
9

Idea
- The chessboard size is fixed at 500 * 500
- 12 directions, 2 searches, one routine
Code
- Note the possible optimization of the second search; when encountering a visited point, directly add the current step count plus [last search answer - stored step count]
- Directly look at the next question, the method is more interesting

HZOJ-401: Strange Chess Game Upgraded Version#

Sample Input

2
12 16
18 10

Sample Output

8
9

Idea
- Search up to 2000 times, the previous method will definitely time out
- ⭐ The endpoint is fixed, start from [1, 1] outward, record an answer array
  - Here, the answer from the starting point to the endpoint is the same as from the endpoint to the starting point, pay attention to the problem statement
- The idea is reversed, similar to problem OJ-398
Code
- Same memset -1, consider the starting point step count as 0
- In this problem, the chessboard is large enough, so there is no need to consider unreachable situations; unreachable generally means the chessboard is too small

HZOJ-303: Matrix Distance One#

Sample Input

Sample Output

3 2 1 0
2 1 0 0
1 0 0 1

Idea
- Input: char! Can be used for boundary checks later
- This distance is actually the number of steps taken one by one
- Similar to the previous problem, the endpoint becomes the starting point, but there are multiple starting points, and this problem has an input map
  - <img src="https://cdn.jsdelivr.net/gh/doubleLLL3/blogImgs@main/img/2020/12/21/21-05-19-d626c41db54a2d81175693ed123f1141-421454.png?fileGuid=VMAPVmz16asV09qg />
  - Start from each starting point, take 1 step in each of the 4 directions, and then move to the next
Code
- <img src="https://cdn.jsdelivr.net/gh/doubleLLL3/blogImgs@main/img/2020/12/21/21-05-17-21bfcc648f8f4d724816cf81f574ffe8-245dba.png?fileGuid=VMAPVmz16asV09qg />
- Similarly, memset initializes num to -1
- Use the answer array for deduplication, keep the map unchanged
  - Can the answer array and the map be unified into one? No, the output needs to use the answer array, which is convenient for outputting -1 and also for understanding

HZOJ-305: Invasion of Milkweed#

Sample Input

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

Sample Output

Idea
- Input: Row and column numbers swapped, starting point coordinates (1, 1) are in the lower left corner
  - Starting point coordinates are also reversed
  - Treat point (1, 1) as point (Y, 1)
  - Principle: Adjust to our coordinate system based on the commonly used coordinate system
- 8 directions
- ⭐ New routine: No endpoint, the result is the maximum distance traversed
  - Termination condition: the queue is empty
  - How to record the farthest step? Use a variable!
Code
- Pay attention to input, deduplication, and recording the farthest step

HZOJ-529: Dragon and Worm#

Sample Input

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

Sample Output

1
Impossible!

Idea
- [Poor] Directly breadth search from the starting point; check after each step: loop through the direction array +1, then check one by one, very many checks
- ⭐ Reverse thinking, but not completely reversed
  - First, start from the enemy, mark all points that can be directly eliminated as [endpoint collection] through the direction array
  - Then breadth search from the starting point, only when the worm [moves to] the endpoint collection can it eliminate the enemy, output the step count at that time
- Multiple sets of data, use a mark array
  - The original map cannot change, and it still needs to be used
  - Use an extra array for marking: mark the endpoint with 1, mark the visited points with 2
  - For each set of data, recreate or clear this array
- Marking the enemy is key
Code
- Problem statement: Coordinates start from [1, 1]
- For [multiple input] data, encapsulate into a function, otherwise need to use a flag to indicate whether to end, as there will be two loops
- The mark array is a local variable, and each input data is brand new
- When breadth searching or traversing the direction array, do not forget your own situation, as it cannot be judged
- Not marking the starting point is also fine, but it will walk through the starting point once more

HZOJ-527: Leap Over the Prairie#

Sample Input

4 4 2
PLLP
PPLP
PPPP
PLLP

Sample Output

Idea
- Starting point: [1, 1]; endpoint: [m, n]
- Flying distance is limited to D, equivalent to total energy
- 【1】 Deduplication needs to add a dimension: remaining energy
  - Because: Data range is small 100; and different remaining energy corresponds to different possible paths, need to distinguish
  - Create a three-dimensional array: point coordinates x y, remaining energy
  - Element value [mark]: just use 0, 1
  - Custom structure also adds a dimension to record the remaining energy at this time
- 【2】 Walk or Fly
  - Flying range: 2 ~ remaining energy, only flying ≥ 2 steps is meaningful; otherwise, walking saves energy
Code
- 【Focus】 Add remaining energy dimension for deduplication, flying method
- Note: Break inside flying
- [PS] When energy is sufficient, this brute-force enumeration method may have some invalid [back-flying] situations, but it will only walk out invalid situations in the optimal step count. This is actually caused by the three-dimensional deduplication array

Although a certain remaining energy coordinate is deduplicated, for cases like PPPPP(12345), if energy is sufficient, there may be paths like 1-3-5-3-5-3

Additional Knowledge Points#

C++ has built-in full permutation functions next_permutation, prev_permutation
- Reference Full permutation function in STL
- But actually not very useful, implementing it oneself is more flexible

Points to Consider#

⭐ Search Routine: 5 Steps#

Store, Start, End, Transform, Revisit [See next chapter: 7 Comprehensive Search Problems]

Tips#

Pathfinding algorithms: You can refer to A* Search Algorithm——Wiki, etc.

Bo2SS