题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路：
最直接的就是搜索了，走迷宫，但想了半个小时还有没有其他解法类似去重啥的，想不出看讨论是搜索。。。
然后开始前要做很多准备工作，打映输出，弄个坐标对象pos（x, y），节点对象（val, flag），将给的两个字符串转为map和list（真不友好）花了半个小时以上。。
然后开始走迷宫一开始被vector引导了朝广搜的思路走，但又没意识到还往深搜靠，结果函数定义的不好（传vector<node>）,又去看了解答意识到了然后写以前最常写的方式，打标去标，又想起讨论区的回溯一说法加上刚才这种做法代码臃肿，于是尝试精简，写成了后续遍历（回溯）,然后彩的一个坑就是xy代表行列和代表坐标的意义是相反的。然后发现这种做法除了可以判断是否可达还可以统计路线总数。花了两个小时。。。。。</node>
#include <iostream> #include <vector> using namespace std;
struct Node{
char val=' ';
int flag=0;
Node(char i){
val = i;
flag = 0;
}
};
struct Pos{
int x;
int y;
Pos(int i, int j){
x=i;
y=j;
}
};
class Solution {
public:
vector<vector<Node>> map;
vector<char> vstr;
/*
void print() {
for (int i = 0; i < map.size();++i) {
for (int j = 0; j < map[0].size(); ++j) {
cout << map[i][j].val << " ";
}
cout << endl;
}
}*/
int search(Pos pos, int index){
if(pos.x<0||pos.x==map.size()||pos.y<0||pos.y==map[0].size())
return 0;
if(map[pos.x][pos.y].flag == 1 ||map[pos.x][pos.y].val != vstr[index])
return 0;
if(index == vstr.size()-1)
return 1;
int sum = 0;
map[pos.x][pos.y].flag = 1;
sum+=search(Pos(pos.x-1, pos.y), index+1); //行列的xy与坐标的xy意义相反
sum+=search(Pos(pos.x, pos.y+1), index + 1);
sum+=search(Pos(pos.x+1, pos.y), index + 1);
sum+=search(Pos(pos.x, pos.y-1), index + 1);
map[pos.x][pos.y].flag = 0;
return sum;
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{
for(int i=0;i<rows;++i){ //繁琐的初始化操作map
vector<Node> row;
for(int j=0;j<cols;++j){
row.push_back(Node(matrix[i*cols+j]));
}
map.push_back(row);
}
for(int i=0;str[i]!='\0';++i) { //转str为vector，
vstr.push_back(str[i]);
}
int sum=0;
for(int i=0;i<rows;++i){
for(int j=0;j<cols;++j){
if(map[i][j].val == vstr[0]){
sum+=search(Pos(i, j), 0); ///
}
}
}
return sum;
}
};int main() {
Solution s;
char a[]={'a','b','c','e','s','f','c','s','a','d','e','e'}, b[] = "bcced";
s.hasPath(a, 3, 4, b);
return 0;
}下面是之前那种最原始的想法实现（模拟搜索），两种的区别在：1.于回溯版本的是只关心当前节点，而下面这个版本是只关心下一个节点是否合法，合法才给进入，所以当前节点是默认合法的了（所以第一次调用要在外围打标除标）其实没回溯好。2.触底的判断这里是用一个块内全局变量来统计不是通过返回值，通过返回值则还是回溯，但代码结构上就特别臃肿了。花了又一个小时。。。
class Solution {
public:
vector<vector<Node>> map;
vector<char> vstr;
void print() {
for (int i = 0; i < map.size();++i) {
for (int j = 0; j < map[0].size(); ++j) {
cout << map[i][j].val << " ";
}
cout << endl;
}
}
int search2_sum = 0; //块内全局记录变量
void search2(Pos pos, int index){
if(index == vstr.size()-1) {
search2_sum++;
return;
}
if(pos.x-1>=0 && map[pos.x-1][pos.y].flag==0 && map[pos.x-1][pos.y].val==vstr[index+1]){
map[pos.x-1][pos.y].flag = 1;
search2(Pos(pos.x-1, pos.y), index+1);
map[pos.x-1][pos.y].flag = 0;
}
if(pos.y+1<map[0].size() && map[pos.x][pos.y+1].flag==0 && map[pos.x][pos.y+1].val==vstr[index+1]) {
map[pos.x][pos.y+1].flag= 1;
search2(Pos(pos.x, pos.y+1), index + 1);
map[pos.x][pos.y+1].flag = 0;
}
if(pos.x+1<map.size() && map[pos.x+1][pos.y].flag==0 && map[pos.x+1][pos.y].val==vstr[index+1]) {
map[pos.x+1][pos.y].flag = 1;
search2(Pos(pos.x+1, pos.y), index + 1);
map[pos.x+1][pos.y].flag = 0;
}
if(pos.x>=0 && map[pos.x][pos.y-1].flag==0 && map[pos.x][pos.y-1].val==vstr[index+1]) {
map[pos.x][pos.y-1].flag = 1;
search2(Pos(pos.x, pos.y-1), index + 1);
map[pos.x][pos.y-1].flag = 0;
}
return ;
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{
for(int i=0;i<rows;++i){
vector<Node> row;
for(int j=0;j<cols;++j){
row.push_back(Node(matrix[i*cols+j]));
}
map.push_back(row);
}
for(int i=0;str[i]!='\0';++i) {
vstr.push_back(str[i]);
}
int sum=0;
for(int i=0;i<rows;++i){
for(int j=0;j<cols;++j){
if(map[i][j].val == vstr[0]){
map[i][j].flag = 1; //第一个节点打标保证进入
search2(Pos(i, j), 0);
map[i][j].flag = 0; //除标
}
}
}
return sum;
}
};
京公网安备 11010502036488号