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