6 Permutations, Combinations, and Searching the Map

——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 point 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 point 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, and n is at most 7
  - Therefore, directly store the result of func(1, 1, 7) and output based on the input n
Code
- First, store the shape array and the starting point positions of the 5 parts

——Permutations and Combinations——#

The three brothers of permutations and combinations: Exponential, Combination, Full Permutation
- Extension
  - 【Combination Problem】 For an array num[100], choose any 5 numbers and output their sum
  - 【Full Permutation Problem】 For an array num[100], output all permutations
  - 【Combination + Full Permutation】 Choose m numbers from n numbers, then fully permute the m numbers, i.e., practice combinations 236 + 237
    - First combine, then fully permute the obtained combinations
  - 【3 Brothers Free Combination】
The time complexity is very high
- Full 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 a layer selects i, 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 for a more backtracking feel → start from which number [put which layer it is in the global variable]
- Note: Unlike version one, the depth cnt here starts from 0, while version one’s deep starts from 1
  - The depth can start from 1 or 0 depending 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 it: add output conditions, output only when m numbers are stored
- Can also use 2 or 3 parameters: add one more output condition, output when the stored depth reaches m
  - 2 parameters feel more backtracking; 3 parameters are easier to understand
Code
- func function uses the 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

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 a 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 a marking array, coordinate marking operations, and the combination of cnt addition and subtraction

——Depth First Search——#

Continuing: Recursion 👉 Permutations and Combinations 👉 Search (Depth First Search)
- Permutations and combinations are actually a form of depth-first 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 First Search Walking the Map——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 marking array], fill with 0 [or check boundaries]

Code

Each time a new point is reached, search again starting from the new point [recursion]
Reaching the endpoint will stop the search early, while unreachable cases will enumerate all paths

HZOJ-535: Tiles#

Sample Input

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

Sample Output

Idea
- Depth-first search, go to the end; breadth-first search can also work
- Note: The order of input h, w
  - The sample has 9 rows and 11 columns, input is 11 9
- How many '.' can be traversed, use a variable ans to store the answer, 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 the wave count, and use it as the starting point to 【depth-first search】 clear the zombies in the same wave
  - Each time a non-zero is passed, set it to 0 to avoid repeated searches later
- Next wave
- The size of the non-zero value here is not useful; 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 question was how many black areas there are; this question is about the size of the largest black area
- 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 that are surrounded by 1s cannot be judged, but 【0s that are not surrounded by 1s】 can be judged!
  - ❗ 0s that are not surrounded by 1s must be connected to the boundary
  - Change the 0s that are not surrounded by 1s to another value: 3
  - 【Output only cares】 when encountering 3 output 0, when encountering 0 output 2
- How to find 0s that are not surrounded by 1s?
  - ❌ Method 1: Traverse the entire outer circle, and when encountering 0, perform depth-first search
    - 【Troublesome】 0s may be divided by 1, resulting in multiple areas, so the entire outer circle must be traversed
  - ⭐ Method 2: Fill with 0, find the 0s connected to the top-left point [0, 0]
    - 【Clever】 These 0s and the 0s that are 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-first search, equivalent to finding the maximum connected area
- Movement method: 0→1, 1→0. That is, only different values can move
- ⭐ Introduce a marking array
  - 【Deduplication】 This scenario uses a marking array for convenience, reducing the number of checks
- 【Cannot fill with 0】 0 has a special purpose in this question, requiring additional boundary checks
Code
- The introduction of the marking array!
- Need to check boundaries because the search condition is to continue only if they are different
  - Although it seems like 0 is filled here, it is actually not used

HZOJ-405: 01 Maze ⭐#

Sample Input

Sample Output

Idea
- Depth-first search
- The difference from the previous question: many queries! Up to 30,000 times
  - If using the previous method, querying each coordinate would definitely time out
- 👇 Space 【Answer Array】 changes time 👇
- Need an extra array to store the answer for each point: ans[3005][3005]
  - ⭐ Additionally, need to use a queue [convenient, stack or array can also work] to store the set of points in a connected area
  - Only after searching through one connected area can we know their answers [the same]
Code
- ❗ The answer array also serves as a marking 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 at the coordinates

——Breadth First Search——#

Can also solve the 【Connectivity】 problem. See HZOJ-396: Fill Color, see the idea above
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, as it is searched layer by layer → Level Order Traversal

Breadth First Search Walking the Map——Basic Template#

Direction array, store the map
Queue [must]: store the points being traversed, without needing recursion; its elements are custom structures that store coordinates and current step count
Deduplication [or marking array], fill with 0 [or check boundaries]

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-first search walking the map
Code
- Deduplication: change to a non-traversable character '.' such as 0

HZOJ-304: Knightly Cow#

Sample Input

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

Sample Output

Idea
- Like the knight's move
- The direction array becomes 8
  - [1, 2] and [2, 1] combinations in four ways each
  - No leg entrapment situation
- Note boundary issues: store from point 2, 2 and check boundaries
- Pitfall: input the number of columns first
Code
- Basic template question, the key is that the direction array has changed

HZOJ-398: Knight 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 using 8 directions
- 【Question】
  - Is it a map? There are no obstacles, just an array
  - How to deduplicate? Similarly, 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 into obstacles, which is troublesome!
- A large array num[405][405]: stores both answers and deduplication
  - 【Question】 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 question start from [1, 1], but boundary checks are still needed because the knight's move must reserve two circles, and no obstacles are set at the boundary
- Use the array num to replace the map, while 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 traversed point, directly use the current step count plus [the last search answer - the 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 idea will definitely time out
- ⭐ The endpoint is fixed, moving outward from [1, 1], recording 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 question
- The idea is reversed, similar to question OJ-398
Code
- Same memset -1, consider the starting point step count as 0
- In this question, the chessboard is large enough, so there is no need to consider unreachable situations; unreachable situations generally occur when 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! It will be useful for checking boundaries later
- This distance is actually the number of steps taken one by one
- Similar to the previous question, the endpoint becomes the starting point, but there are multiple starting points, and this question 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 one step in each of the four 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, keeping 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
  - The 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 state: 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 perform breadth-first search from the starting point; check after each step: loop through the direction array +1, and check one by one, which is very tedious
- ⭐ Reverse thinking, but not completely reversed
  - First start from the enemy, mark all points that can be directly eliminated as 【endpoint set】 through the direction array
  - Then perform breadth-first search from the starting point, only when the worm 【moves to】 the endpoint set can it eliminate the enemy, output the step count at that time
- Multiple sets of data, use a marking array
  - The original map cannot change, and it is still needed
  - Use an extra array for marking: mark the endpoint with 1, mark the traversed points with 2
  - For each set of data, recreate or clear this array
- Marking the enemy is key
Code
- In the question, the 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 marking array is a local variable, and each input data is brand new
- When performing breadth-first search or traversing the direction array, do not forget about 【yourself】, as it cannot be judged
- Not marking the starting point is also fine, but it will take one more step at the starting point

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 one 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 coordinate is deduplicated for a certain remaining energy, for situations like PPPPP(12345), if the energy is sufficient, there will 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