剑指65-矩阵中的路径
2023-02-18 16:41:09 时间
深度遍历,着重复盘
题目描述
{assert_img 1.png 1.png}
解法
虽说是使用深度遍历,但是我没想好要怎么判断字符串是否匹配,所以一下代码时题解看到的,巧妙的时,使用两个数组可以表示上下左右的元素,而且不需要额外数组表示是否遍历过,将遍历过的位置用一个特殊字符’#’替换
代码
class Solution {
public:
int col,row; //定义全局变量
bool hasPath(char* matrix, int rows, int cols, char* str){ //char* matrix 二维数组用一维数组表示
col = cols, row = rows; //为全局变量赋值
for (int i = 0;i < rows;i ++) //先遍历二维数组
for (int j = 0;j < cols; j ++)
if (dfs(matrix, str, 0,i,j)) return true; //查找第一个字符位置,若存在路径则返回true,否则继续循环,查找下个字符
return false;
}
bool dfs(char* matrix, char* str, int u, int x, int y) {
if (u == strlen(str)) return true; //如果字符串的长度等于搜索长度u则返回true
if (matrix[x*col+y] != str[u]) return false; //如果有元素不等则返回false
int dx[4] = {-1, 0, 1, 0},dy[4] = {0, 1, 0, -1}; //(-1,0)up,(0,1)right,(1,0)down,(0,-1)left
char t = matrix[x*col+y]; //将访问过的路径字符赋值给t
matrix[x*col+y] = '*'; //将访问国的路径赋值为'*'
for(int i = 0; i < 4; i ++){
int a = x +dx[i],b = y +dy[i]; //进行上、下、左、右变化后的x,y值
if(dfs(matrix, str, u + 1, a, b)) return true;
}
matrix[x*col+y] = t; //将访问过值放回原矩阵
return false;
}
};
相关文章
- 【架构师(第二十五篇)】编辑器开发之属性编辑区域表单渲染
- 【架构师(第二十六篇)】编辑器开发之属性编辑同步渲染
- 2021年度“CCF-腾讯犀牛鸟基金”发布结题评优结果
- 【架构师(第二十七篇)】前端单元测试框架 Jest 基础知识入门
- 太空噗|重燃太空热潮!与噗噗星人一同探索星海浪漫
- 算法工程师深度解构ChatGPT技术
- 【架构师(第二十八篇)】 测试工具 Vue-Test-Utils 基础语法
- 【架构师(第二十九篇)】Vue-Test-Utils 触发事件和异步请求
- 【架构师(第三十篇)】Vue-Test-Utils 全局组件和第三方库 vuex | vue-router
- 【架构师(第三十一篇)】前端测试之 TDD 的开发方式
- 【架构师(第三十二篇)】 通用上传组件开发及测试用例
- 【架构师(第三十三篇)】 Vue 中的实例及本地图片预览
- 【架构师(第三十四篇)】 业务组件库开发之 vue3 的插件系统
- 【架构师(第三十五篇)】 业务组件库开发之使用 Rollup 进行打包
- 【架构师(第三十六篇)】 业务组件库开发之发布到 NPM
- 【架构师(第四十二篇)】 服务端开发之常用的登录鉴权方式
- 【架构师(第四十三篇)】 服务端开发之单元测试和接口测试
- 【架构师(第四十四篇)】 服务端开发之 pm2 和 nginx 介绍
- 【架构师(第四十六篇)】 服务端开发之安装 Docker
- 【架构师(第四十七篇)】 服务端开发之认识 Docker