# [競程] Where's Waldorf?

###### tags: `競程`

* Online Judge: [10010](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=951)

## 題目
以字串格式給定一個 $m\times n$ 的圖`grid`，每個格子上都有一個字母，大小寫混雜。再給定一個陣列`words`，包含數個字串（忽視大小寫，且保證一定存在圖中），要問這些字串在圖中的分別的起始位置座標（由1開始）。

這些字串可以在圖中可以有八種方向 : 往左、往右、往上、往下、往左上、往左下、往右上、往右下。

## 範例

abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf

words = ["Waldorf", "Bambi", "Betty", "Dagbert"]

輸出的答案會是：

[[2, 5], [2, 3], [1, 2], [7, 8]]

## 思路

這題需要用類似DFS的概念去解決，然而一旦確定了其中一個方向之後，就只能一直持續往相同的方向搜尋，所以需要把一般的尋訪修正一下。事實上比真正的DFS簡單。

在開始編寫程式之前，我們可以先想想，用肉眼直接在圖上面找單字的時候我們會在腦海中建立怎樣的程序，再將這個程序編寫成程式。通常這種方法可以建立出不錯的演算法，再經過些許優化，可能就會是最佳解了。

另外，有以下幾點要注意：
* 題目給定的`grid`是一個字串，可以先轉成list方便做尋訪
* 因為大小寫不拘，所以我們可以把全部的字母都轉換成小寫（或大寫，開心就好，甚至可以是`int`）
* index的計算是由1開始，所以要記得在最後給出的答案上加1
* 若有多個解時，回傳最靠近左上角的解
## 解答
首先我們要對輸入資料進行處理。在這邊我們把所有的字母使用`.lower()`轉換成小寫字元，再使用`ord`函式獲取字母對應的整數編號（例如`ord("a")`是97）：

grid = [[ord(c.lower()) for c in row] for row in grid.split("\n")]
words = [[ord(c.lower()) for c in w] for w in words]

轉成整數的理由是一個整數占用的記憶體空間較小，比較整數也比比較字元快速。

接著我們定義一個`valid_index`函式來檢查一組給定的座標`x, y`是不是在題目給定的圖上合法的座標：

def valid_index(x, y):
    if (x < 0) or (y < 0) or (x >= m) or (y >= n):
        return False
    return True

然後再定義一個`find(x, y, word)`函式，用來檢查word是不是以`x, y`為起始點在這張圖上：

dirs = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]

def find(x, y, word):
    if word[0] != grid[x][y]:
        return False
    for dx, dy in dirs:
        end = True
        for step in range(1, len(word)):
            curr_x = x + dx * step
            curr_y = y + dy * step
            if (not valid_index(curr_x, curr_y)) or (grid[curr_x][curr_y] != word[step]):
                end = False
                break
        if end:
            return True
    return False

在這邊我們先判斷首字母相不相等，以去除大部分不符合的情況。接著我們對八個方向進行迭代。對於每一個可能的方向，我們初始化一個變數`end = True`，如果那個方向走了`step`步，出現不匹配的狀況（`grid[curr_x][curr_y] != word[step]`），或是走到圖的盡頭（`not valid_index(curr_x, curr_y`），就停止往那個方向繼續走，換下一個方向。如果某個特定方向走完了，沒有出現不匹配，那就代表找到了那個字串，直接`return True`。最後，如果每個方向都沒有找到字串，那就是沒有在這點上找到字串了，所以`return False`。

現在我們已經寫好單點的尋訪演算法了，只要對圖上每個點和每個字串執行`find`函式，並把結果收集起來即可：

result = []

for word in words:
    found = False
    for x in range(m):
        for y in range(n):
            found = find(x, y, word)
            if found:
                result.append([x + 1, y + 1])
                break
        if found:
            break

注意這邊的迴圈流程控制，我們使用了一個變數`found`以在找到的狀況跳出對座標的迭代，因為題目要求如果在一張圖上有多個解時，回傳最靠近左上角的，也就是找到的第一個解。

:::spoiler 完整程式碼如下

def find_words(grid, words):
    grid = [[ord(c.lower()) for c in row] for row in grid.split("\n")]
    words = [[ord(c) for c in w.lower()] for w in words]

    m = len(grid)
    n = len(grid[0])

    def valid_index(x, y):
        if (x < 0) or (y < 0) or (x >= m) or (y >= n):
            return False
        return True

    dirs = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]

    def find(x, y, word):
        if word[0] != grid[x][y]:
            return False
        for dx, dy in dirs:
            end = True
            for step in range(1, len(word)):
                curr_x = x + dx * step
                curr_y = y + dy * step
                if (not valid_index(curr_x, curr_y)) or (grid[curr_x][curr_y] != word[step]):
                    end = False
                    break
            if end:
                return True
        return False

    result = []

    for word in words:
        found = False
        for x in range(m):
            for y in range(n):
                found = find(x, y, word)
                if found:
                    result.append([x + 1, y + 1])
                    break
            if found:
                break

    return result



grid = "\
abcDEFGhigg\n\
hEbkWalDork\n\
FtyAwaldORm\n\
FtsimrLqsrc\n\
byoArBeDeyv\n\
Klcbqwikomk\n\
strEBGadhrb\n\
yUiqlxcnBjf\
"

words = ["Waldorf", "Bambi", "Betty", "Dagbert"]

print(find_words(grid, words))
:::