剑指Offer12.矩阵中的路径 C++

1、题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。
在这里插入图片描述
示例 1
输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出:true
示例 2
输入:board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出:false

2、VS2019上运行

使用回溯的方法

#include <iostream>
#include <vector>
using namespace std;class Solution {
public:bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {// 检查当前坐标的字母是否与目标单词中的对应字母相等if (board[i][j] != s[k]) {return false;}// 如果已经匹配到目标单词的最后一个字母,表示找到了路径,返回trueelse if (k == s.length() - 1) {return true;}visited[i][j] = true; // 将当前坐标标记为已访问vector<pair<int, int>> directions{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; // 上、下、左、右四个方向bool result = false; // 用于记录是否找到路径// 依次遍历四个方向for (const auto& dir : directions) {int newi = i + dir.first, newj = j + dir.second; // 计算新坐标// 检查新的坐标是否在矩阵范围内且没有被访问过if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {if (!visited[newi][newj]) {//用于检查位置(newi, newj)是否已经被访问过// 递归调用check函数进行下一步的搜索bool flag = check(board, visited, newi, newj, s, k + 1);if (flag) {result = true; // 如果找到路径,直接返回truebreak;}}}}visited[i][j] = false; // 撤销对当前坐标的标记return result;}bool exist(vector<vector<char>>& board, string word) {int h = board.size(), w = board[0].size(); // 矩阵的行数和列数vector<vector<int>> visited(h, vector<int>(w)); // 记录每个格子的访问状态// 遍历矩阵的每个格子,对每个格子调用check函数for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {bool flag = check(board, visited, i, j, word, 0); // 调用check函数进行搜索if (flag) {return true; // 如果找到路径,直接返回true}}}return false; // 遍历结束后仍未找到路径,返回false}
};int main() {// 示例用法vector<vector<char>> board = {{'A', 'B', 'C', 'E'},{'S', 'F', 'C', 'S'},{'A', 'D', 'E', 'E'}};Solution s;string word = "ABCCED";if (s.exist(board, word)) {cout << "Word exists in the board." << endl;}else {cout << "Word does not exist in the board." << endl;}return 0;
}

Word exists in the board.

3、整体思路

整体的思路是使用深度优先搜索(DFS)算法在矩阵中搜索是否存在与目标单词匹配的路径。

  • 首先,定义一个 check 函数来进行递归的搜索。该函数接收当前的坐标 (i, j)、目标单词 s、以及目前匹配的字符索引 k。函数的返回值是一个布尔值,表示是否找到了匹配的路径。
  • 在 check 函数中,首先进行边界条件的判断。如果当前索引 k 已经匹配到目标单词的最后一个字符,说明已经找到了匹配的路径,返回 true。
  • 接下来,检查当前坐标 (i, j) 处的字母是否与目标单词中的对应字母相等。如果不相等,说明当前路径匹配失败,返回 false。
  • 检查新坐标是否在矩阵的范围内,并且该位置没有被访问过(即 visited[newi][newj] = false)。
    如果满足上述条件,则递归调用 check 函数,在新坐标 (newi, newj) 上继续匹配下一个字符,即 k + 1。
  • 如果递归调用返回 true,表示在某个方向上找到了匹配的路径,直接返回 true。
    如果所有方向的递归调用都没有找到匹配的路径,则撤销对当前坐标 (i, j) 的标记,将 visited[i][j] 设置为 false,表示可以重新访问该位置。
  • 最后,如果所有方向都探索完毕,仍然没有找到匹配的路径,则返回 false,表示没有找到路径。
  • 接下来可以调用 check 函数,从矩阵的每个位置出发,判断是否存在与目标单词匹配的路径。如果返回 true,则说明存在这样的路径;如果返回 false,则说明不存在。
  • 这就是整体的思路,通过DFS算法搜索矩阵中的路径,并利用递归和回溯的思想进行搜索和撤销标记。

4、int h = board.size(), w = board[0].size();

  • 这行代码int h = board.size(), w = board[0].size();的作用是获取二维字符向量board的行数h和列数w。
  • 1.board.size()返回二维字符向量board的行数,即向量中包含的子向量个数。
    2.board[0].size()返回二维字符向量board中第一行子向量的列数,假设矩阵不为空。

5、vector<vector> visited(h, vector(w));

  • 这行代码vector<vector<int>> visited(h, vector<int>(w));创建了一个名为visited的二维整数向量,其大小与输入矩阵board的行数和列数相同。
  • 1.vector<int>(w)部分创建了一个大小为w的整数向量。
  • 2.vector<vector<int>> visited(h, vector<int>(w));使用上述创建的子向量为每一行创建了一个整数向量,从而形成了一个大小为h行、w列的二维整数向量visited。
  • 这样的二维向量visited可以用于跟踪和记录在处理board矩阵时已经访问过的位置或标记。

6、dir.first 和dir.second

  • dir.first表示dir这个pair(键值对)中的第一个元素,即表示方向的行坐标变化。在该上下左右的方向向量中,dir.first表示上下移动的行坐标的变化量。
  • 例如,如果dir是(-1, 0),那么dir.first就是-1,表示向上移动1行。同理,如果dir是(1, 0),那么dir.first就是1,表示向下移动1行。
  • 在搜索一个矩阵的周围方向时,dir.first的值用于计算新的行坐标。通过将当前位置的行坐标i与dir.first相加,可以得到新的行坐标,用于在矩阵中检查相邻位置是否符合要求。

7、visited[i][j] = false;

  • 这行代码为撤销对当前坐标(i, j)的访问标记,将其重新设置为false。
  • 标记的目的是为了跟踪遍历矩阵时已经访问过的位置,以避免重复访问。在代码中,visited向量用于标记位置是否已经被访问过。
  • 当程序进行完成对位置(i, j)的处理后,如果希望在后续的搜索或迭代中能够重新访问该位置,就需要撤销对该位置的访问标记,将visited[i][j]重新设置为false。
  • 撤销对当前坐标的标记允许在后续的遍历或搜索过程中重新考虑访问该位置,以发现其他可能的路径或结果。如果不撤销标记的话,可能会导致某些位置被错误地标记为已访问,从而错过了找到其他路径或结果的机会。因此,需要在适当的时候撤销对当前坐标的标记。

8、for (const auto& dir : directions)

  • for (const auto& dir : directions) 是一个范围-based的循环语句,用于遍历容器 directions 中的元素。
  • 在这个语句中,dir 是一个临时变量,它会依次取到 directions 中的每个元素值。关键字 auto 会自动推断 dir 的类型,使其与 directions 中的元素类型保持一致。const 修饰符表示 dir 是一个常量,即在循环体内不能对它进行修改。
  • 通过这个循环语句,可以依次遍历 directions 容器中的每个方向,执行相应的操作,如计算新坐标 (newi, newj),进行路径匹配等。这样可以依次尝试不同的方向,以搜索矩阵中是否存在与目标单词匹配的路径。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/81779.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

分享一个计算器

先看效果&#xff1a; 再看代码&#xff08;查看更多&#xff09;&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>计算器</title><style>* {box-sizing: border-box;}body…

k8s学习day03

第五章 Pod详解 本章节将详细介绍Pod资源的各种配置&#xff08;yaml&#xff09;和原理。 Pod介绍 Pod结构 每个Pod中都可以包含一个或者多个容器&#xff0c;这些容器可以分为两类&#xff1a; 用户程序所在的容器&#xff0c;数量可多可少 Pause容器&#xff0c;这是每个…

ChatGPT 作为 Python 编程助手

推荐&#xff1a;使用 NSDT场景编辑器 助你快速搭建可编辑的3D应用场景 简单的数据处理脚本 我认为一个好的起点是某种数据处理脚本。由于我打算让 ChatGPT 之后使用各种 Python 库编写一些机器学习脚本&#xff0c;这似乎是一个合理的起点。 目标 首先&#xff0c;我想尝试…

常用开源的弱口令检查审计工具

常用开源的弱口令检查审计工具 1、SNETCracker 1.1、超级弱口令检查工具 SNETCracker超级弱口令检查工具是一款开源的Windows平台的弱口令安全审计工具&#xff0c;支持批量多线程检查&#xff0c;可快速发现弱密码、弱口令账号&#xff0c;密码支持和用户名结合进行检查&am…

第九次作业

1. SSL工作过程是什么&#xff1f; 当客户端向一个 https 网站发起请求时&#xff0c;服务器会将 SSL 证书发送给客户端进行校验&#xff0c;SSL 证书中包含一个公钥。校验成功后&#xff0c;客户端会生成一个随机串&#xff0c;并使用受访网站的 SSL 证书公钥进行加密&#xf…

Effective Java笔记(28)列表优于数组

数组与泛型相比&#xff0c;有两个重要的不同点 。 首先&#xff0c;数组是协变的&#xff08; covariant &#xff09; 。 这个词听起来有点吓人&#xff0c;其实只是表示如果 Sub 为 Super 的子类型&#xff0c;那么数组类型 Sub[ ]就是Super[ ]的子类型。 相反&#xff0c;泛…

linux 安装go 1.18版本

首先去官网找到对应的版本 直接下载下来&#xff08;如果服务器可以直接访问到go 官网也可以wget直接下载到服务器&#xff09; 然后把该包上传到linux 的/usr/local 目录下 然后直接解压安装该包&#xff1a; sudo tar -C /usr/local -zxvf go1.18.10.linux-amd64.tar.gz 然…

Vscode-工具使用

Vscode &#xff0c;这玩意儿是开源的&#xff0c;以前用收费的破解版&#xff0c;过段时间就高版本不匹配&#xff0c;这次搞个不要钱的玩玩&#xff0c;记录使用心得 下载 下载地址&#xff1a;官网 点击下载&#xff0c;但是这里有个问题下载比较慢&#xff0c;解决办法&a…

Dockerfile部署golang,docker-compose

使用go镜像打包&#xff0c;运行在容器内 redis和mysql用外部的 项目目录结构 w1go项目&#xff1a; Dockerfile # 这种方式是docker项目加上 本地的mysql和redis环境 # go打包的容器 FROM golang:alpine AS builder# 为我们镜像设置一些必要的环境变量 ENV GO111MODULEon …

Vue3 第五节 一些组合式API和其他改变

1.provide和inject 2.响应式数据判断 3.Composition API的优势 4.新的组件 5.其他改变 一.provide和inject 作用&#xff1a;实现祖与后代组件间通信 套路&#xff1a;父组件有一个provide选项来提供数据&#xff0c;后代组件有一个inject选项来开始使用这些数据 &…

uniapp 微信小程序 上下滚动的公告通知(只取前3条)

效果图&#xff1a; <template><view class"notice" click"policyInformation"><view class"notice-icon"><image mode"aspectFit" class"img" src"/static/img/megaphone.png"></i…

具有吸引子的非线性系统(MatlabSimulink实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

BIO,NIO,AIO总结

文章目录 1. BIO (Blocking I/O)1.1 传统 BIO1.2 伪异步 IO1.3 代码示例 1.4 总结2. NIO (New I/O)2.1 NIO 简介2.2 NIO的特性/NIO与IO区别1)Non-blocking IO&#xff08;非阻塞IO&#xff09;2)Buffer(缓冲区)3)Channel (通道)4)Selector (选择器) 2.3 NIO 读数据和写数据方式…

刚刚更新win11,记事本消失怎么处理?你需要注意些什么?

记录window11的bug hello&#xff0c;我是小索奇 昨天索奇从window10更新到了window11&#xff0c;由于版本不兼容卸载了虚拟机&#xff0c;这是第一个令脑壳大的&#xff0c;算了&#xff0c;还是更新吧&#xff0c;了解了解win11的生态&#xff0c;后期重新装虚拟机 第一个可…

TCP三次握手四次断开

一、了解TCP &#x1f345;TCP &#xff1a;传输控制协议&#xff0c;是一种面向连接的可靠的传输协议。 什么是可靠的传输协议&#xff1f;如何保障可靠传输&#xff1f; 保证可靠性&#xff1a; 1.确认机制 2.重传输机制什么是面向连接&#xff1f;如何保障面…

教雅川学缠论07-中枢实战众泰汽车000980

本文实战众泰汽车 下面是2023年11月14-2023年8月8众泰汽车日K图 先画日K 接下来处理包含&#xff0c;就变成下面这个样子 下面在套上缠论的理论&#xff0c;未来股价的走势应该是红色椭圆形虚线里面的样子 好了&#xff0c;文章就到这里&#xff0c;如果众泰最终不是这个走势…

人工智能与物理学(软体机器人能量角度)的结合思考

前言 好久没有更新我的CSDN博客了&#xff0c;细细数下来已经有了16个月。在本科时期我主要研究嵌入式&#xff0c;研究生阶段对人工智能感兴趣&#xff0c;看了一些这方面的论文和视频&#xff0c;因此用博客记录了一下&#xff0c;后来因为要搞自己的研究方向&#xff0c;就…

Maven入职学习

一、什么是Maven&#xff1f; 概念&#xff1a; Maven是一种框架。它可以用作依赖管理工具、构建工具。 它可以管理jar包的规模、jar包的来源、jar包之间的依赖关系。 它的用途就是管理规模庞大的jar包&#xff0c;脱离IDE环境执行构建操作。 具体使用&#xff1a; 工作机…

【MATLAB第67期】# 源码分享 | 基于MATLAB的morris全局敏感性分析

【MATLAB第67期】# 源码分享 | 基于MATLAB的morris全局敏感性分析 一、代码展示 clear all npoint100;%在分位数超空间中要采样的点数(计算次数iternpoint*(nfac1) nfac20;%研究函数的不确定因素数量 [mu, order] morris_sa1((x)test_function(x), nfac, npoint)for t1:size…

IELTS图表类作文基础知识

表格可以用table或chart来表示。 其实&#xff0c;数据类图表除了可以用chart表示&#xff0c;也可以用其他单词。 表格又可以称为table。而带有几何图形的图表可以用graph来表示。 像饼状图、折线图、柱状图这样用几何图形&#xff0c;或者直接用表格来呈现数据的形式&#x…