UVA 10010 - Where's Waldorf?

這題是經典的字串搜尋問題（Word Search），需要在一個二維的字元陣列中，尋找指定的單字。搜尋方向包含八個方位（上、下、左、右及四個斜角）。

解題思路

使用一個 directions 陣列來儲存 8 個方向的位移量 (dx, dy)。
針對每一個要尋找的單字，從陣列的左上角開始遍歷每個字元，當首字元相符時，依次往 8 個方向檢查後續字元是否也完全符合。若符合則輸出當前的 1-based 座標。

Python 程式碼

directions = [
    (-1,0),(1,0),(0,-1),(0,1),
    (-1,-1),(-1,1),(1,-1),(1,1)
]

t = int(input())
isFirst = True

for _ in range(t):
    if not isFirst:
        print()
    isFirst = False
    
    emp = input()
    wList = []
    r, c = map(int, input().split())
    
    for _ in range(r):
        wList.append(input().lower())
    
    test = int(input())
    for _ in range(test):
        s = input().lower()
        found = False
        
        for i in range(r):
            for j in range(c):
                if wList[i][j].lower() == s[0]:
                    
                    for dx, dy in directions:
                        match = True
                        
                        for k in range(1, len(s)):
                            nx = i + dx * k
                            ny = j + dy * k
                            
                            if nx < 0 or nx >= r or ny < 0 or ny >= c or wList[nx][ny] != s[k]:
                                match = False
                                break
                                
                        if match:
                            print(f"{i+1} {j+1}")
                            found = True
                            break
                    
                    if found:
                        break
            if found:
                break