[Python] 보글 게임 (BOGGLE)

Algospot에 올라온 보글 게임입니다.

보드판에서 해당하는 알파벳이 있는지 찾아주는 프로그램입니다.

https://algospot.com/judge/problem/read/BOGGLE

Python

xy = [
    (-1,-1),(0,-1),(1,-1),
    (-1,0),        (1,0),
    (-1,1), (0,1), (1,1),
]
    
def find_word_st(dx, dy, wd, index) :
    for (x,y) in xy :
        if dy+y > 4 or dy+y < 0 or dx+x > 4 or dx+x < 0 :
            continue
        
        if board[dy+y][dx+x] is wd[index] :
            if length is index+1 :
                return True
            if find_word_st(dx+x, dy+y, wd, index+1) is True :
                return True

def find_word_ch(wd) :
    global length
    length = len(wd)

    for dy in range(0,5) :
        for dx, ch in enumerate(board[dy]) :
            if wd[0] is ch :
                if find_word_st(dx, dy, wd, 1) is True :
                    return "YES"
    return "NO"

if __name__ == "__main__" :
    global board
    for _ in range(input()) :
        board = []

        for _ in range(0,5) :
            board.append(raw_input())
        
        word = []

        for _ in range(0,input()) :
            word.append(raw_input())

        for wd in word :
            print "{0} {1}".format(wd, find_word_ch(wd))

입력

출력