|
>学习工控知识，就来工控小新
农历十一月二十九日 2024/1/ 10
往期推荐
2024年1月9日，每日花费一分钟练习C语言
2024年1月8日，每日花费一分钟练习C语言
每
日
一
练
/ Daily Exercises
单词搜索
给定一个m x n二维字符网格 board和一个字符串单词word。如果word存在于网格中，返回true;否则，返false。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
题目分析
我们需要在一个二维字符网格中查找一个单词，单词的每个字母必须在相邻的单元格中，而且不能重复使用同一个单元格。这是一个典型的回溯法的问题，也就是说，我们需要尝试不同的路径，直到找到一个符合条件的解，或者遍历所有可能的路径都没有找到解为止。
为了实现回溯法，我们需要定义一个辅助函数，用来递归地在网格中搜索单词的每个字母。这个函数需要接收以下参数：
- board：二维字符网格
- word：要查找的单词
- index：当前要匹配的单词的字母的索引
- x：当前要匹配的网格的行坐标
- y：当前要匹配的网格的列坐标
-visited：一个二维布尔数组，用来记录哪些单元格已经被访问过，避免重复使用
这个函数的返回值是一个布尔值，表示从当前位置开始，能否在网格中找到单词的剩余部分。具体的逻辑如下：
-如果index等于word的长度，说明已经匹配完所有的字母，返回true
-如果x或y越界，或者board[x][y]不等于word[index]，或者visited[x][y]为true，说明当前位置不符合条件，返回false
-否则，将visited[x][y]设为true，表示当前位置已经被访问过
-然后，尝试从当前位置的上、下、左、右四个方向继续搜索，只要有一个方向能够成功，就返回true
-最后，将visited[x][y]设为false，表示当前位置可以被重新访问，返回false
有了这个辅助函数，我们就可以写出主函数，用来遍历网格中的每个位置，作为搜索的起点，调用辅助函数，如果返回true，就说明找到了单词，否则继续遍历，直到遍历完所有位置，如果都没有找到，就返回false。
程序展示
下面是我用C语言写的完整的程序，你可以在VC6.0的环境下运行和调试它：
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <string.h>
// 定义四个方向的偏移量int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};
// 辅助函数，用来递归地在网格中搜索单词的每个字母bool search(char** board, int m, int n, char* word, int index, int x, int y, bool** visited) { // 如果index等于word的长度，说明已经匹配完所有的字母，返回true if (index == strlen(word)) { return true; } // 如果x或y越界，或者board[x][y]不等于word[index]，或者visited[x][y]为true，说明当前位置不符合条件，返回false if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != word[index] || visited[x][y]) { return false; } // 否则，将visited[x][y]设为true，表示当前位置已经被访问过 visited[x][y] = true; // 然后，尝试从当前位置的上、下、左、右四个方向继续搜索，只要有一个方向能够成功，就返回true for (int i = 0; i < 4; i++) { int nx = x + dx; int ny = y + dy; if (search(board, m, n, word, index + 1, nx, ny, visited)) { return true; } } // 最后，将visited[x][y]设为false，表示当前位置可以被重新访问，返回false visited[x][y] = false; return false;}
// 主函数，用来遍历网格中的每个位置，作为搜索的起点，调用辅助函数，如果返回true，就说明找到了单词，否则继续遍历，直到遍历完所有位置，如果都没有找到，就返回falsebool exist(char** board, int m, int n, char* word) { // 创建一个二维布尔数组，用来记录哪些单元格已经被访问过 bool** visited = (bool**)malloc(sizeof(bool*) * m); for (int i = 0; i < m; i++) { visited = (bool*)malloc(sizeof(bool) * n); for (int j = 0; j < n; j++) { visited[j] = false; } } // 遍历网格中的每个位置，作为搜索的起点，调用辅助函数 for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { if (search(board, m, n, word, 0, x, y, visited)) { return true; } } } // 如果都没有找到，就返回false return false;}
// 测试函数，用来创建一个示例的网格和单词，调用主函数，打印结果void test() { // 创建一个示例的网格 char** board = (char**)malloc(sizeof(char*) * 3); board[0] = (char*)malloc(sizeof(char) * 4); board[0][0] = 'A'; board[0][1] = 'B'; board[0][2] = 'C'; board[0][3] = 'E'; board[1] = (char*)malloc(sizeof(char) * 4); board[1][0] = 'S'; board[1][1] = 'F'; board[1][2] = 'C'; board[1][3] = 'S'; board[2] = (char*)malloc(sizeof(char) * 4); board[2][0] = 'A'; board[2][1] = 'D'; board[2][2] = 'E'; board[2][3] = 'E'; // 创建一个示例的单词 char* word = "ABCCED"; // 调用主函数，打印结果 printf("%s\n", exist(board, 3, 4, word) ? "true" : "false");}
// 主程序，调用测试函数int main() { test(); return 0;}
程序测试
为了验证我们的程序是否正确，我们可以用一些测试用例来检验。
源代码获取
#软件下载通道#
我用夸克网盘分享了「20240109」，点击链接即可保存。打开「夸克APP」，无需下载在线播放视频，畅享原画5倍速，支持电视投屏。
链接：https://pan.quark.cn/s/1dc919b2f6cc
(链接和提取码建议复制粘贴，手动输入容易出现错误）
| #支持一下#
分享整理，测试发布不易 如果您方便的话可以帮忙点一下↓↓
谢谢大家！
|
下期题目
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明:本题中，我们将空字符串定义为有效的回文串
示例 1:
输入:"A man，aplan，acanal: Panama
输出: true
解释:“amanaplanacanalpanama”是回文串示例 2:
输入:"race acar"
输出: false
点赞加关注，学习不迷路
微信公众号｜工控小新
EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中
发现“分享”和“赞”了吗，戳我看看吧
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
