Problem 10010 Where's Waldorf?，找字串

給你一雜亂無章的字元陣列，要你從這字元陣列中，找尋出一些相符字串。只是搜尋字串必須朝著某一方向進行，例如：
要找尋底下四個字串
Waldorf
Bambi
Betty
Dagbert
而在底下陣列出現之位置如變色所在：

abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf

上面例子已經很清楚的顯示，搜尋字串必須朝某一方向，不能彎來彎去，而輸出要輸出字串符合的開頭位置：
2 5
2 3
1 2
7 8

此題要用遞迴來解決，但是一旦決定方向，便不再改變。寫一函式嘗試核對字串，傳入陣列位置 i, j，以及找尋字串目前索引 index 和方向的編號 id(此數決定該往何方向核對字串)，C 語言程式碼如下：

#define SIZE 51

char W[SIZE][SIZE];
char str[200];
int row, col, isFind, len;

void searchStr(int i, int j, int index, int id)
{ 
    if (W[i][j] != str[index]) return;
    if (isFind || index == len - 1) {isFind = 1; return;}
    else
    {
        /* 左 */
        if (j - 1 >= 0 && (!id || id == 1)) 
            searchStr(i, j - 1, index + 1, 1);
        /* 左上 */
        if (j - 1 >= 0 && i - 1 >= 0 && (!id || id == 2)) 
            searchStr(i - 1, j - 1, index + 1, 2);
        /* 上 */
        if (i - 1 >= 0 && (!id || id == 3)) 
            searchStr(i - 1, j, index + 1, 3);
        /* 右上 */
        if (j + 1 < col && i - 1 >= 0 && (!id || id == 4)) 
            searchStr(i - 1, j + 1, index + 1, 4);
        /* 右 */
        if (j + 1 < col && (!id || id == 5)) 
            searchStr(i, j + 1, index + 1, 5);
        /* 右下 */
        if (j + 1 < col && i + 1 < row && (!id || id == 6)) 
            searchStr(i + 1, j + 1, index + 1, 6);
        /* 下 */
        if (i + 1 < row && (!id || id == 7)) 
            searchStr(i + 1, j, index + 1, 7);
        /* 左下 */
        if (j - 1 >= 0 && i + 1 < row && (!id || id == 8)) 
            searchStr(i + 1, j - 1, index + 1, 8);
    }
}

上段程式面，str 為找尋字串，W 為字元陣列。

最後，只須在主程式如此呼叫：

gets(str);
len = strlen(str); 
for (j = 0; j < len; j ++)
    str[j] = tolower(str[j]);
isFind = 0;
for (j = 0; j < row && !isFind; j ++)
    for (s = 0; s < col && !isFind; s ++)
    {
        searchStr(j, s, 0, 0);
        if (isFind) printf("%d %d\n", j + 1, s + 1);
    }

By David.K

p10010題目連結
回ACM題庫目錄
回首頁