牛客网中矩阵中的路径
2019-10-25 06:24:57来源:博客园 阅读 ()
牛客网中矩阵中的路径
牛客网的题目如下:
题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径,
但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。
解决思想:
- 首先找到访问的起点,就是目标字符串的第一个字符与矩阵中的该字符的所有位置找出来。
- 使用bfs,将起点位置,上下左右,都去访问,每访问矩阵中一个字符的时候,会判断该字符是否合法,合法性的判断标准为:
字符所在的位置,行x,列y,属于矩阵中,该字符没有已经被访问过, - 如果该字符和目标字符串的当前需要访问的字符相同,说明当前字符有可能是路径中的一员,需要保存当前访问的信息,并放入队列,当访问它的邻居的时候,
就可以把当前访问的下标,拿来使用, - 只要访问矩阵节点的保存的下标,与字符串的最后一个字符的下标相同,说明目前字符串中的字符完全访问完毕,路径就表示找到。
实现的代码
本文实现的代码,只能满足牛客网的测试用例,当测试用例较全的时候,该代码无法通过,但可以用于学习下bfs,
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
struct MyPoint {
int x;
int y;
int index;
MyPoint(int x1, int y1, int k):x(x1), y(y1), index(k) {
}};
class Solution {
public:
int row;
int col;
char *ma;
char *s;
bool hasPath(char *matrix, int rows, int cols, char *str) {
if ((*str) == '\0')
return false;
row = rows;
col = cols;
ma = matrix;
s = str;
vector < int >xs;
vector < int >ys;
int k;
int sLen = strlen(str);
int *visits = new int[rows * cols];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++) {
k = i * cols + j;
if (matrix[k] == str[0]) {
xs.push_back(i);
ys.push_back(j);
}
} int xLen = xs.size();
for (int i = 0; i < xLen; i++) {
memset(visits, 0, sizeof(int) * rows * cols);
visits[xs[i] * col + ys[i]] = 1;
if (bfs(visits, xs[i], ys[i], 0, sLen))
return true;
}
return false;
}
bool bfs(int *visits, int startX, int startY, int curIndex, int sLen) {
static int dx[] = { 0, 1, 0, -1 };
static int dy[] = { -1, 0, 1, 0 };
queue < MyPoint * >q;
MyPoint *p0 = new MyPoint(startX, startY, curIndex);
q.push(p0);
while (!q.empty()) {
MyPoint *p1 = q.front();
q.pop();
printf("x=%d y=%d index=%d\n", p1->x, p1->y, p1->index);
if (p1->index == (sLen - 1))
return true;
for (int i = 0; i < 4; i++) {
int xx = dx[i] + p1->x;
int yy = dy[i] + p1->y;
int kk = xx * col + yy;
if (visitIsLegal(xx, yy, visits)
&& ma[kk] == s[p1->index + 1]) {
MyPoint *p2 = new MyPoint(xx, yy, p1->index + 1);
visits[kk] = 1;
q.push(p2);
}
}
}
return false;
}
bool visitIsLegal(int x, int y, int *visits) {
if (x < 0 || x >= row)
return false;
if (y < 0 || y >= col)
return false;
int k = x * col + y;
if (visits[k])
return false;
return true;
}
};
int main()
{
char *matrix = "AAAAAAAAAAAA";
// char *str="AAAAAAAAAAAA";
char *str = "AAAAAAAAA";
int row = 3, col = 4;
Solution s;
cout << "res = " << s.hasPath(matrix, row, col, str) << endl;
}
原文链接:https://www.cnblogs.com/wanshuafe/p/11732235.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:c++ 内存二进制表示
下一篇:小白的C++之路——求质数
- 稀疏矩阵类 2020-06-09
- 重载矩阵加法运算 代码参考 2020-04-29
- 螺旋矩阵问题 2020-04-18
- 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的 2020-04-15
- 快速幂与矩阵快速幂 2020-01-27
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash