华为公司校招软件开发工程师-上机笔试题.docx

Word Maze是一个网络小游戏，你需要找到 以字母标注的食物，但要求以给定单词字母的 顺序吃掉。如上图，假设给定单词if，你必 须先吃掉i然后才能吃掉f。
但现在你的任务可没有这么简单，你 现在处于一个迷宫Maze〔nxm的矩阵〕当 中，里面到处都是以字母标注的食物，但你只 能吃掉能连成给定单词W的食物。
如下列图，指定W为“SOLO ，则在地图中红 色标注了单词“SOLO 。
CPUCY
EKLQH
CRS0L
FAIA0
PGRBC
注意区分英文字母大小写，你只能上下左右行 走。
运行时间限制：
无限制
内存限制：
无限制
输入：
输入第一行包含两个整数n、m(0 <n, m<21)分别表示n行m列的 矩阵，第二行是长度不超过1 的单词W,从第3行到底n+3行 是只包含大小写英文字母的长度 为m的字符串。
输出：
如果能在地图中连成给定的单
词，则输出“YES ，否则输出
“NO 。注意：每个字母只能用 一次。
5 5

SOLO
CPUCY
样例输入:
EKLQH
CRSOL

EKLQO
PGRBC
样例输出：
YES
答案提示：

bool maze(char array[21][21], int m, int n,
char *word)
{

int i, j, w=0;
int x, y;
for (i=0; i<m; i++)
{
x = i;
for (j=0; j<n; j++)
{
y = j;
if (array[x][y] == word[w])
{
while ('\0' != word[w])
w++;
if ((x>0) && (x<m-1) && (y>0) && (y<n-1))
{
if (array[x-1][y] == word[w])
{
x = x-1;
}
else if (array[x+1][y] == word[w])
{
x = x+1;
}
y = y-1;
}
else if (array[x][y+1] == word[w])
{
y = y+1;
}
else
break;
}
else if ((x<m-1) && (y>0) && (y<n-1))
{
if (array[x+1][y] == word[w])
{
x = x+1;
}
else if (array[x][y-1] == word[w])
{
y = y-1;
}
else if (array[x][y+1] == word[w])
{
y = y+1;
}
else
break;
}
else if ((x>0) && (y>0) && (y<n-1))
{
x = x-1;
}
else if (array[x][y-1] == word[w])
{
y = y-1;
}
else if (array[x][y+1] == word[w])
{
y = y+1;
}
else
break;
}
else if ((x>0) && (x<m-1) && (y<n-1))
{
if (array[x-1][y] == word[w])
{
x = x-1;
}
else if (array[x+1][y] == word[w])
{
x = x+1;
}
else if (array[x][y+1] == word[w])
{
y = y+1;
}
else
break;
}
else if ((x>0) && (x<m-1) && (y>0))
{
if (array[x-1][y] == word[w])
{
x = x-1;
}
else if (array[x+1][y] == word[w])
{
x = x+1;
}
else if (array[x][y-1] == word[w])
{
y = y-1;
}
else
break;
}
else if ((x<m-1) && (y<n-1))
{
if (array[x+1][y] == word[w])
{
x = x+1;
}
else if (array[x][y+1] == word[w])
{
y = y+1;
} else
break;
}
else if ((x<m-1) && (y>0))
{
if (array[x+1][y] == word[w])
{
x = x+1;
}
else if (array[x][y-1] == word[w])
{
y = y-1;
}
else
break;
}
else if ((x>0) && (y<n-1))
{
if (array[x-1][y] == word[w])
{
x = x-1;
}
else if (array[x][y+1] == word[w])
{
y = y+1;
}
else
break;
}
else if ((x>0) && (y>0))
x = x-1;
}
else if (array[x][y-1] == word[w])
{
y = y-1;
}
else
break;
}
}
if ('\0' == word[w])
{
return 1;
}
}
}
}
return 0;
}
int main(void)
{
int m, n;
char word[1];
char input[21][21] = {'0'};
scanf("%d %d", &m, &n);
scanf("%s", word);
for (int i=0; i<m; i++)
scanf("%s",input[i]);
//
//
//
//
//
//
//
}
for (int k=0; k<m; k++)
{
for (int l=0; l<n;l++)
{
printf("%c",input[k][l]);
}
}
bool b = maze(input, m, n, word);
if (1 == b)
{
printf("YES\n");
}
else
{
printf("NO\n");
} return 0;