矩阵中的路径 剑指offer65题
2024-09-03 11:40:19
include "stdafx.h"
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<stack>
using namespace std;
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
vector<vector<bool>> visited(rows, vector<bool>(cols,false));
vector<vector<char>> mat(rows, vector<char>(cols, 'a'));
vector<char> s;
for (int i = 0;i < rows;i++)
{
for (int j = 0;j < cols;j++)
{
mat[i][j] =matrix[ i*cols + j];
}
}
for (int i = 0;i < strlen(str);i++)
{
s.push_back(str[i]);
}
bool flag = false;
for (int i = 0;i < rows;i++)
{
for (int j = 0;j < cols;j++)
{
if (mat[i][j] == str[0])
{
if (getPath(mat, i, j, s, 0, visited) == true)
{
flag = true;
break;
}
}
if (flag == true)
{
break;
}
}
}
return flag;
}
bool getPath(vector<vector<char>> mat, int rows, int cols, vector<char> s,int num, vector<vector<bool>> visited)
{
if (num == s.size() - 1 && mat[rows][cols] == s[num])
return true;
if (mat[rows][cols] == s[num])
{
visited[rows][cols] = true; //已经被访问
num++;
bool left = false;
bool right = false;
bool up = false;
bool down = false;
//向左走
if (cols - 1 >= 0 && visited[rows][cols - 1] == false)
left = getPath(mat, rows, cols - 1, s, num, visited);
//向右走
if (cols + 1 < mat[0].size() && visited[rows][cols + 1] == false)
right = getPath(mat, rows, cols + 1, s, num, visited);
//向上走
if (rows - 1 >= 0 && visited[rows - 1][cols] == false)
up = getPath(mat, rows - 1, cols, s, num, visited);
//向下走
if (rows + 1 < mat.size() && visited[rows + 1][cols] == false)
down = getPath(mat, rows + 1, cols, s, num, visited);
visited[rows][cols] = false;
return left || right || up || down;
}
else
{
return false;
}
}
};
int main()
{
Solution s;
cout << s.hasPath("ABCESFCSADEE", 3, 4, "ABCCED") << endl;
return 0;
}最新文章
- angular源码分析：angular中jqLite的实现——你可以丢掉jQuery了
- AngularJS_对象数组-filter-orderBy
- 七：zookeeper与paxos的分析
- Red Hat Linux认证
- WPF 多线程处理(6)
- Ansible好像很好玩的样子哟
- 自定义一个searchBar
- （原）ubuntu16中编译boost1.61.0库
- 将 Shiro 作为应用的权限基础 一：shiro的整体架构
- 云计算之路-阿里云上-容器难容：优化自建 docker swarm 集群的部署
- Fibonacci数列的解法
- 在 .NET Core 中结合 HttpClientFactory 使用 Polly（上篇）
- IDEA 对比eclipse环境调节
- jenkins持续集成：构建多个job同时执行
- Django之Models(二)
- css3 伸缩布局 display:flex等
- java4/9 异常处理
- 安装 scws出现 autoconf 需要先安装
- windows7 Cygwin 下安装 YouCompleteMe 插件
- jquery ajax contentType设置