华为机试【6、找到它】

6、标题:找到它
【找到它】找到它是一个小游戏，你需要在一个矩阵中找到给定的单词。假设给定单词 HELLOWORD， 在矩阵中只要能找到 H->E->L->L->O->W->O->R->L->D连成
的单词，就算通过。注意区分英文字母大小写，并且您只能上下左右行走，不能走回头路
输入描述:
输入第1行包含两个整数 n、m(0<n,m<21)分别表示 n行m列的矩阵，
第2行是长度不超过100的单词W(在整个矩阵中给定单词 W 只会出现一次)，
从第3行到第n+2行是指包 含大小写英文字母的长度为 m的字符串矩阵。
输出描述:
如果能在矩阵中连成给定的单词，则输出给定单词首字母在矩阵中的位置(第几行 第几列)，否则输出“NO”。
示例:
输入
5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC
输出
3 2

def find_it():
    # 给数据一个固定的默认值方便调试
    # n, m = 5, 5
    # s = "HELLOWORLD"
    # arr = ["CPUCY", "EKLQH", "CHELL", "LROWO", "DGRBC"]
    n, m = tuple([int(x) for x in input().strip().split(" ")])
    s = input().strip()
    arr = []
    for i in range(n):
        arr.append(input().strip())

    def loc_surroundings(loc):
        """按上、右、下、左顺序输出坐标周围的合法坐标"""
        loc_up = (loc[0] - 1, loc[1])
        loc_right = (loc[0], loc[1] + 1)
        loc_below = (loc[0] + 1, loc[1])
        loc_left = (loc[0], loc[1] - 1)
        surroundings = []
        for location in [loc_up, loc_right, loc_below, loc_left]:
            if 0 <= location[0] <= n - 1 and 0 <= location[1] <= m - 1:
                surroundings.append(location)
        return surroundings

    def search_path(start_loc, s_index, tmp_result, result):
        """回溯"""
        if s_index > len(s) - 2:
            result.append(tmp_result[:])
            return
        for surround_loc in loc_surroundings(start_loc):
            # 不能走回头路
            if surround_loc != start_loc and surround_loc not in tmp_result and \
                    arr[surround_loc[0]][surround_loc[1]] == s[s_index + 1]:
                tmp_result.append(surround_loc)
                search_path(surround_loc, s_index + 1, tmp_result, result)
                tmp_result.pop()

    tmp_result, result = [], []
    # 找到起点符合的坐标，开始回溯
    for i in range(m):
        for j in range(n):
            if arr[i][j] == s[0]:
                tmp_result.append((i, j))
                search_path((i, j), 0, tmp_result, result)
                if result:
                    return i+1, j+1


print(find_it())