文章作者：姜南(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;
}
}
}
}
}
