python-穿越雷区

解题思路:

深度搜索。

①定位A点的坐标

②开始搜索，依次搜索上下左右是否能走，若能，则走。

③直到找到B，判断所用步长是否最小，若是，更新最小值。

注意事项:

参考代码:

from cmath import inf  
  
def dfs(x,y,space):  
    global n  
    global Graph  
    global sign  
    global minspace  
  
    if Graph[x][y] == 'B':       #判断是否到大B点，若到达，判断所用步长是否最小
        if space < minspace:  
            minspace = space  
        return  
      
    temp = Graph[x][y]        #记录这一位置的符号  
    if temp == 'A':  
        if 0<=x-1<=n-1 and 0<=y<=n-1 and sign[x-1][y]:  
            sign[x-1][y] = 0    #此处要进行标记，已经走过
            dfs(x-1,y,space+1)  
            sign[x-1][y] = 1    #注意！！！不要忘记进行搜索之后将这一点走过的标记抹除，不然这点只能走一次
        if 0<=x+1<=n-1 and 0<=y<=n-1 and sign[x+1][y]:  
            sign[x+1][y] = 0  
            dfs(x+1,y,space+1)  
            sign[x+1][y] = 1  
        if 0<=x<=n-1 and 0<=y-1<=n-1 and sign[x][y-1]:  
            sign[x][y-1] = 0  
            dfs(x,y-1,space+1)  
            sign[x][y-1] = 1  
        if 0<=x<=n-1 and 0<=y+1<=n-1 and sign[x][y+1]:  
            sign[x][y+1] = 0  
            dfs(x,y+1,space+1)   
            sign[x][y+1] = 1  
    else:  
        if 0<=x-1<=n-1 and 0<=y<=n-1 and Graph[x-1][y] != temp and sign[x-1][y]:  
            sign[x-1][y] = 0  
            dfs(x-1,y,space+1)  
            sign[x-1][y] = 1  
        if 0<=x+1<=n-1 and 0<=y<=n-1 and Graph[x+1][y] != temp and sign[x+1][y]:  
            sign[x+1][y] = 0  
            dfs(x+1,y,space+1)  
            sign[x+1][y] = 1  
        if 0<=x<=n-1 and 0<=y-1<=n-1 and Graph[x][y-1] != temp and sign[x][y-1]:  
            sign[x][y-1] = 0  
            dfs(x,y-1,space+1)  
            sign[x][y-1] = 1  
        if 0<=x<=n-1 and 0<=y+1<=n-1 and Graph[x][y+1] != temp and sign[x][y+1]:  
            sign[x][y+1] = 0  
            dfs(x,y+1,space+1)       
            sign[x][y+1] = 1      
  
  
  
if __name__ == '__main__':  
    n = int(input().strip())  
    Graph = [[j for j in input().strip().split()] for i in range(n)]  
    sign = [[1 for j in range(n)] for i in range(n)]    #标记，用来判断这一点是否走过
    xa = 0  
    ya = 0  
    for i in range(n):           #定位A点坐标
        for j in range(n):  
            if Graph[i][j] == 'A':  
                xa = i  
                ya = j  
                break  
    sign[xa][ya] = 0  
    minspace = inf  
    dfs(xa,ya,0)        #开始搜索
    print(minspace)