锐客网

  1. 首页 > it技术 > >

华为机试|20150802厦门大学华为校园提前批招聘机试体验题三（Word Maze（单词迷宫））

c华为机试

题三：
（样题，已对外公布）Word Maze(单词迷宫)
描述:
华为机试|20150802厦门大学华为校园提前批招聘机试体验题三（Word Maze（单词迷宫））
文章图片



Word Maze 是一个网络小游戏，你需要找到以字母标注的食物，但要求以给定单词字母的顺序吃掉。如上图，假设给定单词if，你必须先吃掉i然后才能吃掉f。

但现在你的任务可没有这么简单，你现在处于一个迷宫Maze（n×m的矩阵）当中，里面到处都是以字母标注的食物，但你只能吃掉能连成给定单词W的食物。

如下图，指定W为“SOLO”，则在地图中红色标注了单词“SOLO”。
华为机试|20150802厦门大学华为校园提前批招聘机试体验题三（Word Maze（单词迷宫））
文章图片



注意区分英文字母大小写,你只能上下左右行走。

运行时间限制: 无限制
内存限制: 无限制
输入: 输入第一行包含两个整数n、m(0
输出: 如果能在地图中连成给定的单词，则输出“YES”，否则输出“NO”。注意：每个字母只能用一次。

样例输入: 5 5
SOLO
CPUCY
EKLQH
【华为机试|20150802厦门大学华为校园提前批招聘机试体验题三（Word Maze（单词迷宫））】CRSOL
EKLQO
PGRBC
样例输出: YES


本题用到的算法为穷举求解，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。在求迷宫通路的算法中应用“栈”较为方便。本人采用的是递归方法。


代码如下：


#include using namespace std; int n, m; //行、列数 char maze[100][21] = { {'\0'} }; //字母矩阵 char w[101] = { '\0' }; //待查找的单词 int len = 0; //待查找单词的长度 int flag[100][21] = { { 0 } }; //二维位置标志 int a[4] = { 0, 0, -1, 1 }, b[4] = { 1, -1, 0, 0 }; //设置行、列变换路径：行只能向上向下、列只能向左向右 int findit = 0; //是否找到单词标志int search(int p, int q, int k)//递归查找 { int i, s, t; if (k == len)//所有字母都找完，则是否找到单词的标志置1，返回 { findit = 1; return 0; } flag[p][q] = 1; //找到，该位置标志置1 for (i = 0; i < 4; i++) { s = p + a[i]; //改变行 t = q + b[i]; //改变列 if (s >= 0 && s < n && t >= 0 && t < m && flag[s][t] == 0 && maze[s][t] == w[k]) //查找字母位置在矩阵内，且该位置未被查找过，同时找到字母 search(s, t, k + 1); //寻找下一个字母 } flag[p][q] = 0; //没找到，该位置标志重新置0 return 0; }int main() { int i, j; cin >> n >> m; //输入行、列数 cin.get(); //取掉回车符 cin.getline(w, 100); //输入待查找的单词 len = strlen(w); //待查找单词的长度 for (i = 0; i < n; i++) { cin.getline(maze[i], 21); //输入字母矩阵 } for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (maze[i][j] == w[0])//找到首字母 { flag[i][j] = 1; //找到，该字母标志置1 search(i, j, 1); //查找 flag[i][j] = 0; //没找到，该字母位置标志重新置0 } } } if (findit == 1)//连成给定的单词 cout << "YES" << endl; else//未连成给定的单词 cout << "NO" << endl; return 0; }



    推荐阅读


    上一篇：Eigen使用总结

    下一篇：SCARA 机器人概述