最新消息:点击查看大S的省钱秘笈

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

编程相关 Slyar 5627浏览 14评论

文章作者:姜南(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,不过没有什么高深算法,就是一个简单的深搜,上面的那堆就是测试数据,效果自己编译运行看去…

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

#include 
#include 

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;
                }
            }
        }
    }
}

转载请注明:Slyar Home » 纵横单词(Crossword Puzzles)查找 C++版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (14)

  1. 大神..怎么作词库啊...
    yy19928年前 (2012-12-09)回复
  2. 求c版本呀~~~
    jessie9年前 (2012-04-24)回复
  3. @sdfjsldfjldjfld 那您打算让我怎么办....=_=
    Slyar11年前 (2010-02-07)回复
  4. 您很牛摆啊。。。“效果自己运行去。。”
    sdfjsldfjldjfld11年前 (2010-02-06)回复
  5. 嗯,我过来围观CC老师的。 话说雷顿教授真的不错玩~
    Jet11年前 (2009-10-24)回复
  6. @cissyhope 貌似木有,我不记得我上次写过递归...恩,我去下载...
    Slyar11年前 (2009-10-24)回复
  7. 去年珠海赛有个差不多的题,你做过么? 另外建议去玩雷顿教授三部曲,里面一堆题目让人有写代码解决的欲望。
    cissyhope11年前 (2009-10-24)回复
  8. @SoleilNeon 下面不是给出了单词列表嘛...
    Slyar11年前 (2009-10-18)回复
  9. 不太明白怎么样判断找到的单词就是一个有意义的单词而不是没有意义的字母组合,应该有个什么字典的吧...
    SoleilNeon11年前 (2009-10-18)回复
  10. @Slyar 我觉得应该还好,写过两遍就差不多了,主要是一直没有去写。。
    felix02111年前 (2009-10-17)回复
  11. 楼主NB,
    hdlover11年前 (2009-10-17)回复
  12. @felix021 那个太难了吧...
    Slyar11年前 (2009-10-17)回复
  13. 应该用trie...不过我也不大会。。
    felix02111年前 (2009-10-17)回复