锐客网

  1. 首页 > it技术 > >

单词查找（公司笔试题）

题目：单词查找 分析：题目限制了字母在词典中只可以上下左右相邻，那就意味着不能左上、右上、左下、右下、那就 比起八个方向的就更加简单。具体实现就深搜呗~具体细节在代码的注释 单词查找（公司笔试题）
文章图片

单词查找（公司笔试题）
文章图片

测试样例：
【单词查找（公司笔试题）】5 5 3
hello help high
p a b h m
f h e c p
o i l l h
b g h o n
h x c m l

// wordfind.cpp: 定义控制台应用程序的入口点。 //#include "stdafx.h" #include #include #include #define MAXN 10000 using namespace std; int M, N; char array1[MAXN][MAXN]; //读入的单词 char Str[MAXN][MAXN]; //单个字母表 bool vis[MAXN][MAXN]; //搜索时访问标志数组 int mov[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; bool BFS(int x , int y , int num , int u ) //x,y：搜索的起始坐标 num:第num个单词 u:单词中的第U个字符 { vis[x][y] = true; //访问过的位置即标记为true if (u == strlen(array1[num])) return true; for (int j = 0; j < 4; j++) { int new_x = x + mov[j][0]; int new_y = y + mov[j][1]; //x y 向新的方向移动if (new_x >= 0 && new_x < N && new_y >= 0 && new_y < M && !vis[new_x][new_y] && Str[new_x][new_y] == array1[num][u]) //new_x,new_y没有越界&&vis数组的对应位置没有被访问&&对应的字符相匹配 { bool flag = BFS(new_x, new_y, num, u + 1); if (flag) return true; } } return false; } int main() { int K; while (scanf("%d%d%d",&M,&N,&K)!=EOF) {for (int i = 0; i < K; i++) scanf("%s", array1[i]); char temp[2]; for (int i = 0; i < N ; i++) { for (int j = 0; j < M; j++) { scanf("%s", temp); Str[i][j] = temp[0]; } } for (int kk = 0 ; kk < K ; kk++) { memset(vis, 0, sizeof(vis)); bool flag = false ; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (Str[i][j] == array1[kk][0]) //找到单个单词的匹配的首字符，然后继续向后搜索 { flag = BFS(i, j, kk, 1); if (flag) break; else memset(vis, 0, sizeof(vis)); } } if (flag) break; } if (flag) printf("%s\n", array1[kk]); } } return 0; }


    推荐阅读


    上一篇：netty的编解码器介绍

    下一篇：hive|python连接hive配置