数据结构与算法解析习题1.2：编写一个程序求解字谜游戏问题。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

static char puzzle[4][4] = {
    {'t','h','i','s'},
    {'w','a','t','s'},
    {'o','a','h','g'},
    {'f','g','g','t'}
};

static char *dict[4] = {"this","two","fat","that"};

int wordExist(int x, int y, int dir, int strlen, char *word, int (*position)[2]);

int main() {
    char word[5];
    int position[4][2];
    int x, y, dir, strlen;

    for(x = 0; x < 4; x++) {
        for(y = 0; y < 4; y++) {
            for(dir = 0; dir < 8; dir++) {
                for(strlen = 2; strlen < 5; strlen++) {
                    // 坐标 x y
                    // 方向 dir
                    // 单词长度从2开始
                    if(wordExist(x, y, dir, strlen, word, position) == 1) {
                        printf("word: %s\n",word);

                        printf("posotin ：");

                        for (int i = 0; i < 4; ++i) {
                            printf("%d,%d  ", position[i][0], position[i][1]);
                        }

                        printf("\n");

                        break;
                    }
                }
            }
        }
    }

    return 0;
}


int wordExist(int x, int y, int dir, int strlen, char *word, int position[][2])
{
    // 先清空位置信息,-1为无效位置
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 2; ++j) {
            position[i][j] = -1;
        }
    }

    char sword[5];
    int i = 0, j;
    while(i < strlen) {
        position[i][0] = x;
        position[i][1] = y;
        sword[i++] = puzzle[x][y];
        sword[i] = '\0';
        for(j = 0; j < 4; j++) {
            // 如果字符串相同
            if(strcmp(sword,dict[j]) == 0) {
                strcpy(word,dict[j]);
                return 1;
            }
        }

        switch (dir) {
            case 0:        //从左到右
                y++;
                break;
            case 1:        //从右到左
                y--;
                break;
            case 2:        //从上到下
                x++;
                break;
            case 3:        //从下到上
                x--;
                break;
            case 4:        //从左上到右下
                x++;
                y++;
                break;
            case 5:        //从右下到左上
                x--;
                y--;
                break;
            case 6:        //从左下到右上
                x--;
                y++;
                break;
            case 7:        //从右上到左下
                x++;
                y--;
                break;
            default:
                puts("Direction error.");
                return 0;
        }

        if(x < 0 || y < 0)
            return 0;
    }
    return 0;
}