首页 > 其他分享 >offer68题 Day3

offer68题 Day3

时间:2024-10-29 23:09:03浏览次数:1  
标签:index const target int Day3 dfs offer68 grid

面试题 12. 矩阵中的路径

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

class Solution
{
public:
	bool exist(vector<vector<char>>& grid, const string& target )const
	{
		const int m=grid.size();    // 行数
		const int n=grid[0].size(); // 列数

		// index是字串target中单个字符的索引
		function<int(int,int,int)> dfs=[&](const int i,const int j,const int index)->int
		{
			if(index==target.length()){ return true; } // 如果目标单词的所有字母都找到了,返回 true
			// 越界检查及当前单元格字母是否匹配,或已经被访问过
			if(i<0||i>=m || j<0||j>=n || grid[i][j]!=target[index]){ return false;}

			// 标记当前位置为已访问
			const char tmp=grid[i][j];
			grid[i][j]='#';

			// 递归搜索四个方向:下、上、右、左
			const bool found = dfs(i+1,j,index+1) ||
				dfs(i-1,j,index+1) ||
				dfs(i,j+1,index+1) ||
				dfs(i,j-1,index+1);

			// 恢复当前位置
			grid[i][j]=tmp;

			return found;
		};


		// 遍历 grid 中的每个字符,作为起点开始 DFS
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if (dfs(i,j,0)) return true;
			}
		}
		return false;  // 如果所有路径都没有找到目标单词,返回 false
	}

};


int main()
{
	Solution solution;
	vector<vector<char>> grid = {
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'C', 'S'},
		{'A', 'D', 'E', 'E'}
	};
	string target = "ABCCED";

	if (solution.exist(grid, target)) {
		cout << "The word '" << target << "' exists in the grid.\n";
	} else {
		cout << "The word '" << target << "' does not exist in the grid.\n";
	}

	return 0;
}

标签:index,const,target,int,Day3,dfs,offer68,grid
From: https://www.cnblogs.com/itsinsane/p/18514495

相关文章

  • Offer68题 Day2 树的基础算法
    1.前中后序递归遍历//前序遍历classSolution{public:voidtraversal(TreeNode*cur,vector<int>&vec){if(cur==NULL)return;vec.push_back(cur->val);//中traversal(cur->left,vec);//左traversal(cur-&g......
  • Offer68题 Day3 两个基础算法
    1.DFS深度优先算法/* -深度优先算法 DFS从起始节点出发,沿着一条路径尽可能深入地访问每个节点,直到无法继续时再回退,寻找未访问的节点。 -使用递归实现。*/#include<iostream>#include<vector>usingnamespacestd;voidDFS(intnode,vector<vector<int>>&gra......
  • 代码随想录算法训练营day30| 452. 用最少数量的箭引爆气球 435. 无重叠区间 763.
    学习资料:https://programmercarl.com/0452.用最少数量的箭引爆气球.html重叠区域问题最远位置问题452.用最少数量的箭引爆气球(重叠区域;按左边界排序;i区间的左边界与i-1区间的右边界比较来确定是否重叠;更新i的右边界,取i与i-1区域右边界的最小值)点击查看代码classSolution(ob......
  • 代码随想录一刷-day3
    T209长度最小子数组核心:滑动窗口思想,如何用一个for循环达到两个循环的效果for(intj=0;j<num.size();j++){sum+=nums[j];//外层for循环内负责将窗口结束的坐标++;while(sum>=target){window_length=j-i+1;result=min(result,window_length);sum-=nums[i++];......
  • offer68题 Day2
    面试题07.重建二叉树前中序构建要根据二叉树的前序遍历和中序遍历结果来构建二叉树,我们可以利用以下性质:前序遍历的第一个元素总是当前树的根节点。中序遍历中,根节点将二叉树分为左子树和右子树。思路根据前序遍历的第一个元素确定根节点。在中序遍历中找到根节点位置......
  • 网络编程(Day34)
    一、学习内容网络发展历史发展阶段1.APRAnet阶段---冷战产物2.TCP/IP协议阶段--只有TCP和IP两个协议3.osi开放系统互联模型4.TCP/IP协议族(重要)5.量子通信(可能)TCP/IP两个协议阶段概念在计算机网络中,要做到有条不紊的交换数据,需要遵循一些事先约定好的规则......
  • 代码随想录算法训练营Day39 | 卡玛网-46.携带研究材料、416. 分割等和子集
    目录卡玛网-46.携带研究材料416.分割等和子集卡玛网-46.携带研究材料题目卡玛网46.携带研究材料(第六期模拟笔试)题目描述:小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包......
  • I\O进程线程(Day31)
    一、学习内容线程的同步互斥机制同步机制之条件变量概念1>条件变量实现的是一个生产者对多个消费者问题2>条件变量本质上维护了一个队列,所有消费者线程想要执行之前先要进入该队列中。等待生产者线程来唤醒。先进入等待队列中的线程被先唤醒。由于,对于消费者而言,这......
  • Offer68题 Day1
    LCR120.寻找文件副本classSolution{//offer03public:intfindRepeatDocument(vector<int>&documents){//方法:哈希表,查找元素是否存在unordered_set<int>vsi;for(inti=0;i<documents.size();i++){if(vsi.count(documents......
  • 代码随想录打卡Day3
    链表:通过指针链接的线性数据结构。链表由两部分组成,一为数据域,一为指针域。并与结构体有很大关系,链表的节点一般都是结构体,其中包含了该节点的数据部分以及指向下一节点的指针。通过这种方式,链表将结构体与指针连接起来,从而构建一个强大的数据结构,可以同时实现数据的组织和动......