Blue Bridge Cup DFS (I)

maze

X  A labyrinth playground on the planet is built on a hillside . It is from  10×10  Made up of interconnected small rooms .

 There is a big letter on the floor of the room . Let's assume that the player is standing facing uphill , be ：

L  Go to the room on the left ,
R  Go to the room on the right ,
U  It means walking up the slope ,
D  It means going downhill .
X  The inhabitants of the planet are a little lazy , Not willing to think . They prefer to play games of luck . The same is true of this game ！

 At the beginning , Helicopter handle  100  Players into a small room . Players must move according to the letters on the ground .

 The map of the maze is as follows ：

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
 Please calculate , Last , How many players will walk out of the maze , Instead of going around in circles ？

 If you don't understand the rules of the game , See the following simplified  4x4  Explanation of the maze ：

 Picture description 

 Operation limit 
 Maximum operation time ：1s
 Maximum running memory : 128M

analysis

• dfs: First, store the data in a file , Then read every line in the file , By converting a string into a list , Make the elements in each line independent , That is, there are multiple characters in the list added to each line , In this way, we can Build a two-dimensional list （ Of course , Here, you can also use input and other methods to build , As long as it can be built ）
• establish Of the same size Tag array ,0 It means you haven't gone yet ,1 Indicates walking
• First Determine termination conditions ： namely Transboundary It proves that we can go out , Return 1
• If you walk past , That is, it is marked with , It means that the cycle is entered , You can't go out , Natural return as 0
• First of all, I have to go to this point , The tag array marks this point as 1, If you go up, down, left and right （UDLR）, Enter the corresponding dfs, Pay attention to enter the corresponding dfs need return.
• First , Let's be clear , If you just write into recursion , If the outermost recursion does not get a return, it will return void, therefore To enter recursion return Recursive function . Someone might ask ：“ Why is the previous backtracking algorithm used , no need return What about recursive functions ？”, as a result of ： Add the result to the list before , The list is an iteratable object , The simple understanding is that the default is a global variable .
• therefore , If you only recurse without return Words , We can directly define global variables in the function and then output them
• Of course , Backtracking here is actually very violent , Look at each cycle and reset the space to 0 You know the , But small-scale problems can be calculated at will , Even this problem is very simple

Code （return Recursive function ）

file_list = [] #  Store file data 
with open('1.txt','r') as file:
    for i in file.readlines():
        file_list.append(list(i.strip()))

flag = [[0]*10 for _ in range(10)] # 0 Not yet ,1 Gone through 

def dfs(x,y):
    if x < 0 or x > 9 or y < 0 or y > 9:
        return 1

    if flag[x][y] == 1:
        return 0
    
    flag[x][y] = 1
    
    if file_list[x][y] == 'U':        
        return dfs(x-1,y)
    
    elif file_list[x][y] == 'D':
        return dfs(x+1,y)
    
    elif file_list[x][y] == 'L':
        return dfs(x,y-1)
    
    elif file_list[x][y] == 'R':
        return dfs(x,y+1)

res = 0
for i in range(10):
    for j in range(10):
        flag = [[0]*10 for _ in range(10)] # 0 Not yet ,1 Gone through 
        res+=dfs(i,j)

print(res)

Through screenshots

Code （ No return Recursive function ： Define global variables ）

file_list = [] #  Store file data 
with open('1.txt','r') as file:
    for i in file.readlines():
        file_list.append(list(i.strip()))

flag = [[0]*10 for _ in range(10)] # 0 Not yet ,1 Gone through 

def dfs(x,y):
    global res
    if x < 0 or x > 9 or y < 0 or y > 9:
        res+=1
        return 

    if flag[x][y] == 1:
        return 
    
    flag[x][y] = 1
    
    if file_list[x][y] == 'U':        
        dfs(x-1,y)
    
    elif file_list[x][y] == 'D':
        dfs(x+1,y)
    
    elif file_list[x][y] == 'L':
        dfs(x,y-1)
    
    elif file_list[x][y] == 'R':
        dfs(x,y+1)

res = 0
for i in range(10):
    for j in range(10):
        flag = [[0]*10 for _ in range(10)] # 0 Not yet ,1 Gone through 
        dfs(i,j)
        

print(res)

Through screenshots （ Get the right answer ）

Manual calculation

• From the outermost layer , Green is going out , Red means you can't go out , Count and you will know that the green grid has 31 individual . This method is simpler than programming , We count from the outermost layer , Gradually expand to the innermost layer , If all the peripheries have been unable to get out , The interior can't go out , But the periphery can be reached , It doesn't have to be internal , such as ： Up and down , And left and right as two pairs of contradictory groups , If the corresponding orientation of two grids is this case , Will always be wandering in these two grids .
  

Grid segmentation

 Title Description 
 This question is to fill in the blanks , Just calculate the result , Use the output statement in the code to output the filled results .

6x6 Of the lattice , Cut in two along the edge of the grid .  The shape of the two parts should be exactly the same .

 Here are three possible segmentation methods .

 Try to calculate ：  Including this  3  The method of seed division is inside , How many different segmentation methods are there .  Be careful ： Rotationally symmetric belongs to the same segmentation method .

 Operation limit 
 Maximum operation time ：1s
 Maximum running memory : 128M

analysis

• It is not difficult to see from the graph , All satisfied graphs are about （3,3） symmetry , This is the most important breakthrough in this topic . hypothesis , There's a graph that doesn't include boundaries , The other figure must include all the boundaries , But the two figures are not equal . therefore , We can turn the problem into drawing the cutting line and reverse cutting line from the center point （ If there is a reverse cutting line, it will avoid the cutting line walking in the position of the reverse cutting line ）, Calculate how many ways to reach the boundary .
• Because the four directions of this figure rotate uniformly , So in the end it must be divisible 4 Of
• Termination conditions ： If the cutting line exceeds the boundary, it ends , And record the addition of 1 Ways of planting .
• Tag path ： Cut lines and reverse cut lines are marked as 1
• loop ： Search in four directions , Get new x and y. If the new x and y Beyond the boundary , Then prune （continue）, If the new coordinate point has not been accessed , Into recursion .
• Finally, add the condition of backtracking , The path is marked as 0

Code

res = 0
dir = [(-1,0),(1,0),(0,-1),(0,1)] #  Up, down, left and right （ Two dimensional array ）

vis = [[0]*7 for _ in  range(7)] #  It means you haven't left yet 

def dfs(x,y):

    global res
     #  Termination conditions 
    if x == 0 or x == 6 or y == 0 or y == 6:
        res+=1
        return
    vis[x][y] = vis[6-x][6-y] = 1 #  The mark has passed 

    for i in range(4):
        new_x = x + dir[i][0]
        new_y = y + dir[i][1]

        if new_x < 0 or new_x > 6 or new_y < 0 or new_y > 6:
            continue #  prune 

        if not vis[new_x][new_y]: #  If the new coordinate point is not accessed 
            dfs(new_x,new_y)

    #  to flash back ( The marked object is x,y)
    vis[x][y] = vis[6-x][6-y] = 0

dfs(3,3)
print(res//4)

Through screenshots

The answer is 509

If there is a mistake , Please correct me , Welcome to exchange , thank you *(･ω･)ﾉ