首页 > 编程相关 > 纵横单词(Crossword Puzzles)查找 C++版

纵横单词(Crossword Puzzles)查找 C++版

2009年10月16日 22:58 Slyar 发表评论 阅读评论

文章作者:Slyar 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

周四的外教课,我们那个澳大利亚籍外教给了一个小朋友玩的游戏 -- Crossword Puzzles。规则就是先给你一个由字母组成的矩阵,里面隐藏了很多单词,之后再给你一排单词,让你把这些单词在矩阵里画出来...

11 11
r e h t o r b b r y g
y r e h t o m e a r z
l e l n n o h t a w r
i t c b i t z n w e g
m s n y a s d a u n t
a i u f n p u w e f e
f s w n a m t o r o w
u i c r t p r l c x p
t g e n d c e b s x u
u n c l r m z f e m a
t w q r v t o h c y t

9
aunt
brother
cousin
family
father
grandparent
mother
sister
uncle

恩,大概就是这么个意思。不过我最近比较烦啊,哪里有心情去一个一个找,还不说这些单词可以正向,可以反向,可以斜着...大爷没空

烦躁的时候就想写代码,顺手就把这个小游戏敲完了,懒得写printf和scanf,就用C++的cin和cout,不过没有什么高深算法,就是一个简单的深搜,上面的那堆就是测试数据,效果自己编译运行看去...

我发这个代码纯属凑文章数...

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <string>
 
using namespace std;
 
const int MAX = 20;
 
/* 定义矩阵的长和宽 */
int width, height;
 
/* 定义矩阵 */
char map[MAX][MAX];
 
/* 定义标记矩阵 */
bool ext[MAX][MAX];
 
/* 定义方向数组 */
int dir[8][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {-1,-1}, {1,-1}, {-1,1}};
 
/* 定义当前符合字符的个数 */
int step;
 
/* 函数声明 */
void Input(); 
void Output();
void Dfs(string, int, int, int);
void FindWords(string);
 
/* 主函数 */
int main()
{
    cin >> height >> width; 
 
    Input();
 
    int n;
    cin >> n;
    while (n--)
    {
        string str;
        cin >> str;
        FindWords(str);
    }
    cout << endl;
 
    Output();
 
    system("pause");
}
 
/* 读入矩阵函数 */
void Input()
{
    int i, j;
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            cin >> map[i][j];
        }
        cin.get();
    }
}
 
/* 输出矩阵函数 */
void Output()
{
    int i, j;
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            if (ext[i][j] == true)
            {
                cout << map[i][j] << " ";
            }
            else
            {
                cout << "  ";
            }
        }
        cout << endl;
    }    
}
 
/* Dfs搜索单词 */
void Dfs(string str, int i, int j, int k)
{
    /* 符合字符数+1 */
    step++;
    /* 找到单词就退出递归 */
    if (step == str.size())
    {
        /* 标记找到单词 */
        ext[i][j] = true;
        return;
    }
    int x, y;
    /* 向一个方向一直找下去 */
    x = i + dir[k][0];
    y = j + dir[k][1];
    /* 如果字符相同则继续递归搜索(注意要防止数组下标越界) */
    if (x >= 0 && x < width && y >= 0 && y < height && map[x][y] == str[step])
    {
        Dfs(str, x, y, k);
        /* 标记找到单词 */
        if (step == str.size()) ext[i][j] = true;
    }
}
 
/* 找出单词 */
void FindWords(string str)
{
    int i, j;
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            /* 如果首字符相同才搜索 */
            if (map[i][j] == str[0])
            {
                int k;
                /* 分别向八个方向搜索 */
                for (k = 0; k < 8; k++)
                {
                    step = 0;
                    Dfs(str, i, j, k);
                    /* 找到单词就立刻返回 */
                    if (step == str.size()) return;
                }
            }
        }
    }
}
分类: 编程相关 标签: ,
  1. 2010年2月7日12:58 | #1

    @sdfjsldfjldjfld 那您打算让我怎么办....=_=

  2. 2010年2月6日16:33 | #2

    您很牛摆啊。。。“效果自己运行去。。”

  3. 2009年10月24日23:29 | #3

    嗯,我过来围观CC老师的。
    话说雷顿教授真的不错玩~

  4. 2009年10月24日14:37 | #4

    @cissyhope 貌似木有,我不记得我上次写过递归...恩,我去下载...

  5. cissyhope
    2009年10月24日14:30 | #5

    去年珠海赛有个差不多的题,你做过么?
    另外建议去玩雷顿教授三部曲,里面一堆题目让人有写代码解决的欲望。

  6. 2009年10月18日22:39 | #6

    @SoleilNeon 下面不是给出了单词列表嘛...

  7. 2009年10月18日18:58 | #7

    不太明白怎么样判断找到的单词就是一个有意义的单词而不是没有意义的字母组合,应该有个什么字典的吧...

  8. felix021
    2009年10月17日12:48 | #8

    @Slyar 我觉得应该还好,写过两遍就差不多了,主要是一直没有去写。。

  9. 2009年10月17日12:24 | #9

    楼主NB,

  10. 2009年10月17日11:28 | #10

    @felix021 那个太难了吧...

  11. felix021
    2009年10月17日09:09 | #11

    应该用trie...不过我也不大会。。

bnuep:0801010047