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')