WordMaze单词迷宫C语⾔解法（详细注解）
Word Maze单词迷宫C语⾔解法（详细注解）
c语言编程小游戏
题⽬描述
Word Maze 是⼀个⽹络⼩游戏，你需要到以字母标注的⾷物，但要求以给定单词字母的顺序吃掉。假设给定单词if，你必须先吃掉i然后才能吃掉f。
但现在你的任务可没有这么简单，你现在处于⼀个迷宫Maze（n×m的矩阵）当中，⾥⾯到处都是以字母标注的⾷物，但你只能吃掉能连成给定单词W的⾷物。
注意区分英⽂字母⼤⼩写，并且你只能上下左右⾏⾛。
输⼊
输⼊第⼀⾏包含两个整数n、m(0<n,m<21)分别表⽰n⾏m列的矩阵，第⼆⾏是长度不超过100的单词W，从第3⾏到第n+2⾏是只包含⼤⼩写英⽂字母的长度为m的字符串。
输出
如果能在地图中连成给定的单词，则输出“YES”，否则输出“NO”。注意：每个字母只能⽤⼀次。
C语⾔代码
#include <stdio.h>
#include <string.h>
/*也可不建⽴全局变量，将相关数组⽤指针的⽅式传递到函数中进⾏操作*/
int n, m;
char str[100];
char array[21][21];
int visit[21][21] = {0}; //记录已过的字母位置
int DFS(int i, int j, int k, int length)
{
/
*判断是否到达单词尾部，若到达表⽰已到*/
if (k == length)
{
return 1;
}
/*判断是否到达边界*/
if ((i >= n) || (j >= m) || (i < 0) || (j < 0))
{
return 0;
}
/*判断该单词是否过*/
if (visit[i][j] == 1)
return 0;
/*若当前矩阵中的字母与对应单词⼀致，继续往下搜索*/
if (array[i][j] == str[k])
{
/*将搜索过的位置进⾏标记*/
visit[i][j] = 1;
/*若已到返回1*/
if (DFS(i + 1, j, k + 1, length) || DFS(i - 1, j, k + 1, length) || DFS(i, j + 1, k + 1, length) || DFS(i, j - 1, k + 1, length))            return 1;
else
{
/*未到，将之前标记⾛过的位置抹掉*/
visit[i][j] = 0;
}
}
/*若当前矩阵中的字母与对应单词不⼀致，返回0*/
return 0;
}
int main()
{
scanf("%d %d", &n, &m);
scanf("%s", str);
for (int i = 0; i < n; i++)
{
scanf("%s", array[i]);
}
int length = strlen(str);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int flag = DFS(i, j, 0, length);
if (flag == 1)
{
printf("YES\n");
return 0;
}
}
}
printf("NO");
return 0;
}
DFS算法
在使⽤DFS算法解决问题时，⾸先需要考虑如下三个问题：
1. 是否有条件不成⽴的信息
2. 是否有条件成⽴的信息
3. 是否需要标记已访问的节点
结合该题，针对以上三个问题分析：
1. 条件不成⽴信息主要包括：
a. 当前迷宫中的字符与单词中的字符不⼀致
b. 到达边界
2. 条件成⽴的信息主要包括：当前已搜索到单词尾部，说明已在迷宫中到该单词
3. 是否需要标记节点：需要。对已经访问的节点进⾏记录，同时注意当该路径⾛不通返回时，要将之前标记的节点信息抹掉。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。