牛客網的題目如下：
題目描述
請設計一個函式，用來判斷在一個矩陣中是否存在一條包含某字串所有字符的路徑，路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子，
如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子， 例如 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;
}
dfs解法
bfs演算法不適合，是因為把相鄰的節點，都訪問了，如果，目標串有很多相同的字符，會造成，其中的一些字符以后不會再訪問了，
從而目標串中字符未訪問完畢，所以本題目的正確解法，用深度優先搜索，每訪問完，目標字串中的字符，就需要訪問它的下一字符，
對應為矩陣中，該字符的四周，當找到路徑時，就不需要再去查找了，要從下往上回傳true,就可以了，這個要注意哈
dfs 的代碼如下
#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;
// cout<<"xs[i]"<<xs[i]<<" ys[i] "<<ys[i]<<endl;
if (dfs(visits, xs[i], ys[i], 0, sLen))
return true;
}
return false;
}
bool dfs(int *visits, int startX, int startY, int curIndex, int sLen) {
static int dx[] = { 0, 1, 0, -1 };
static int dy[] = { -1, 0, 1, 0 };
if(curIndex >= (sLen-1) )
return true;
// cout<<"startX ="<<startX<<" startY ="<<startY<<" curIndex = "<<curIndex<<endl;
for (int i = 0; i < 4; i++) {
int xx = dx[i] + startX;
int yy = dy[i] + startY;
int kk = xx * col + yy;
/*
if(startX == 0 && startY ==2){
cout<<"visits[3] ="<<visits[3]<<endl;
cout<<"xx= "<<xx<<" yy="<<yy<<endl;
cout<<"ma[kk]= "<<ma[kk]<<" s="<<s[curIndex+1]<<endl;
cout<<"visit index="<<visitIsLegal(xx, yy, visits)<<endl;
}
*/
if (visitIsLegal(xx, yy, visits)
&& ma[kk] == s[curIndex + 1]) {
visits[kk] = 1;
/*
if(xx == 0 && yy==3 && startX == 0 && startY ==2){
cout<<"ok"<<endl;
cout<<"index+1"<<curIndex+1<<endl;
}
*/
bool flag = dfs(visits,xx,yy,curIndex+1,sLen);
if( flag == true)
return true;
visits[kk] = 0;
}
}
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.uj5u.com/houduan/93392.html
標籤：C++
下一篇：OI之路