Python Word Maze解决方案

def GetWordMazeInputList():
    inputList = []
    inputSearchStr = ''

    try:
        inputnum = input().strip().split()
        if not type(inputnum) == list:
            return

    except EOFError:
        print("input num error")

    try:
        inputStrList = input().strip().split()

        if type(inputStrList) == list:
            inputSearchStr = inputStrList[0]
    except EOFError:
        print("input num error")

    while True:
        try:
            inputval = input().strip().split()

            if type(inputval) == list:
                inputList.append(inputval[0])
            else:
                inputList.append(inputval)

            if len(inputList) == int(inputnum[0]):
                break

        except EOFError:
            break

    return inputnum, inputSearchStr, inputList

# 判断当前list是否和前面的posVal连续
def JudgeTwoListIsContinue(prePosValList, curList):
    rtVal = False
    CurPosValList = []
    CurPosInforList = []

    for prePosVal in prePosValList:
        for index in range(len(curList)):
            NxtPosVal = curList[index][3]
            absVal = abs(NxtPosVal - prePosVal)
            if absVal == 1:
                CurPosVal = NxtPosVal
                if CurPosVal not in CurPosValList:
                    CurPosValList.append(CurPosVal)
                # 返回pos信息
                CurPosInforList.append((curList[index][1], curList[index][2]))
                rtVal = True

    return rtVal, CurPosValList, CurPosInforList

def ProcWordMazeInputList(inputnum, inputSearchStr, inputList):
    searchchrList = []
    #
    charListList = []
    for index in range(len(inputList)):
        charList = list(inputList[index])
        charListList.append(charList)

    lineNum = int(inputnum[0])
    rowNum = int(inputnum[1])

    #
    searchchrList = list(inputSearchStr)

    # 搜索标记的元素
    # [0] = char, [1] = lineIndex, [2] = rowIndex, [3] = posVal, [4] Up, [5] Down, [6] Left, [7] Right, [8] behind con, [9] front con
    markedEleList = []

    for lineIndex in range(0, lineNum):
        for rowIndex in range(0, rowNum):
            if charListList[lineIndex][rowIndex] in searchchrList:
                markedEle = []
                markedEle.append(charListList[lineIndex][rowIndex])
                markedEle.append(lineIndex)
                markedEle.append(rowIndex)
                posVal = int(markedEle[1]) + int(markedEle[2])
                markedEle.append(posVal)
                # 初始化方向链接信息
                markedEle.append(False)
                markedEle.append(False)
                markedEle.append(False)
                markedEle.append(False)
                markedEle.append(False)
                markedEle.append(False)
                markedEle.append([])
                markedEleList.append(markedEle)


    # 标记元素间链接关系
    for index in range(0, len(markedEleList)):
        markedEle = markedEleList[index]
        targetVal = markedEle[3] + 1
        filterlist = filter(lambda x: int(x[3]) == targetVal, markedEleList)
        for filterEle in filterlist:
            # right
            if int(filterEle[2]) == int(markedEle[2]) + 1:
                markedEle[7] = True
                filterEle[6] = True
            # down
            elif int(filterEle[1]) == int(markedEle[1]) + 1:
                markedEle[5] = True
                filterEle[4] = True

    # 标记元素间是否按照查找字符串的顺序连接
    # searchcharOff = 0
    # 边界
    for searchcharOff in range(0, len(searchchrList)):
        filterlist = filter(lambda x: x[0] == searchchrList[searchcharOff], markedEleList)

        for markedEle in filterlist:

            # Up
            if markedEle[4] == True:
                targetChar = charListList[markedEle[1] - 1][markedEle[2]]
                if searchcharOff < (len(searchchrList) - 1):
                    if targetChar == searchchrList[searchcharOff + 1]:
                        markedEle[8] = True
                        markedEle[10].append((markedEle[1] - 1, markedEle[2]))
                if searchcharOff > 0:
                    if targetChar == searchchrList[searchcharOff - 1]:
                        markedEle[9] = True

            # Down
            if markedEle[5] == True:
                targetChar = charListList[markedEle[1] + 1][markedEle[2]]
                if searchcharOff < (len(searchchrList) - 1):
                    if targetChar == searchchrList[searchcharOff + 1]:
                        markedEle[8] = True
                        markedEle[10].append((markedEle[1] + 1, markedEle[2]))
                if searchcharOff > 0:
                    if targetChar == searchchrList[searchcharOff - 1]:
                        markedEle[9] = True

            # Left
            if markedEle[6] == True:
                targetChar = charListList[markedEle[1]][markedEle[2] - 1]
                if searchcharOff < (len(searchchrList) - 1):
                    if targetChar == searchchrList[searchcharOff + 1]:
                        markedEle[8] = True
                        markedEle[10].append((markedEle[1], markedEle[2] - 1))
                if searchcharOff > 0:
                    if targetChar == searchchrList[searchcharOff - 1]:
                        markedEle[9] = True

            # Right
            if markedEle[7] == True:
                targetChar = charListList[markedEle[1]][markedEle[2] + 1]
                if searchcharOff < (len(searchchrList) - 1):
                    if targetChar == searchchrList[searchcharOff + 1]:
                        markedEle[8] = True
                        markedEle[10].append((markedEle[1], markedEle[2] + 1))
                if searchcharOff > 0:
                    if targetChar == searchchrList[searchcharOff - 1]:
                        markedEle[9] = True

    # 检查搜索字符串链接关系
    LastSearchCharlistList = []
    rtVal = True

    LastSearchCharlist = list(filter(lambda x: (x[0] == searchchrList[0]) and (x[8] == True), markedEleList))
    LastSearchCharlistList.append(LastSearchCharlist)

    filterlist = list(filter(lambda x: (x[8] == True) and (x[9] == True), markedEleList))
    for searchcharOff in range(1, len(searchchrList) - 1):
        LastSearchCharlist = list(filter(lambda x: x[0] == searchchrList[searchcharOff], filterlist))
        if len(LastSearchCharlist):
            LastSearchCharlistList.append(LastSearchCharlist)
        else:
            rtVal = False
            print(searchcharOff, "empty")
            break

    if rtVal == True:

        LastSearchCharlist = list(filter(lambda x: (x[0] == searchchrList[len(searchchrList) - 1]) and (x[9] == True), markedEleList))
        LastSearchCharlistList.append(LastSearchCharlist)

        # 检查符号间连续性
        funcRtVal = CheckListIsContinue(LastSearchCharlistList)

        # 如果连续,排查路径是否重叠
        if funcRtVal == True:
            funcRtVal = CheckListOrderIsValid(LastSearchCharlistList, len(searchchrList))



        rtVal = funcRtVal

    #print(rtVal)
    return rtVal

def CheckListIsContinue(LastSearchCharlistList):
    prePosValList = []
    ProcPosInforList = []
    ProcPosInforListList = []

    for markedEle in LastSearchCharlistList[0]:
        prePosValList.append(markedEle[3])
        ProcPosInforList.append((markedEle[1], markedEle[2]))

    ProcPosInforListList.append(ProcPosInforList)
    #

    funcRtVal = True
    for index in range(1, len(LastSearchCharlistList)):
        # 循环调用子函数,子函数用来判断连续性,并刷新当前pos值
        rtVal, rtPosValList, rtPosInforList = JudgeTwoListIsContinue(prePosValList, LastSearchCharlistList[index])

        if rtVal == True:
            ProcPosInforListList.append(rtPosInforList)

            prePosValList = rtPosValList
        else:
            funcRtVal = False
            break

    return funcRtVal

# 重试回跳点,每次探测失败时弹出一个,每次探测成功时如果有其他路径,压栈
popPointList = []
# 当前尝试路径,每次探测后刷新
curPathList = []
OriPosInforList = []
PosLinkInforDic = {}

def CheckListOrderIsValid(LastSearchCharlistList, searchDeepth):

    funcRtVal = False

    for LastSearchCharlist in LastSearchCharlistList:
        OriPosInfor = []
        for markedEle in LastSearchCharlist:
            OriPosInfor.append((markedEle[1], markedEle[2]))
            PosLinkInforDic[(markedEle[1], markedEle[2])] = markedEle[10]
        OriPosInforList.append(OriPosInfor)

    # 初始化尝试point
    for posInfor in OriPosInforList[0]:
        posList = []
        posList.append(posInfor)
        posList.append(0)

        popPointList.append(posList)

    for index in range(0, searchDeepth):
        curPathList.append('null')

    while(len(popPointList)):
        startPosList = popPointList.pop()

        rtVal = StartProbe(startPosList[0], startPosList[1], searchDeepth)

        if (curPathList[searchDeepth - 1] != 'null'):
            funcRtVal = True
            break


    return funcRtVal

# pos不在当前路径中
def StartProbe(pos, preDeepth, searchDeepth):

    hasPath = False

    if (pos in OriPosInforList[preDeepth]) and (pos not in curPathList):
        curPathList[preDeepth] = pos

        if pos in PosLinkInforDic.keys():
            nextPosList = PosLinkInforDic[pos]
            curDeepth = preDeepth + 1

            hasPath = False
            # 将下一级信息全部压栈
            for nextPos in nextPosList:
                # 检查是否在路径中,如果在,跳过
                if nextPos not in curPathList:
                    hasPath = True
                    posList = []
                    posList.append(nextPos)
                    posList.append(curDeepth)
                    popPointList.append(posList)

    return hasPath

 

if __name__ == "__main__":

    inputnum, inputSearchStr, inputList = GetWordMazeInputList()

    rtVal = ProcWordMazeInputList(inputnum, inputSearchStr, inputList)

    if rtVal == True:
        print('YES')
    else:
        print('NO')
上一篇:HDU -1010 Tempter of the Bone(DFS)


下一篇:回溯法写迷宫(C++编写)