【数据结构与算法】回溯法

一.回溯的基本原理

就像我们上次找的迷宫的出口一样,道路千万条,我们必须要尝试,走不通的路我们就回来走下一条路.

上次我们用的是栈去实现求解的迷宫的问题,现在我们去使用递归的方式来达到回退的方式,来完成一个字符串路径的问题.

二.字符串路径

1.问题

在一个字符矩阵中看某个字符串是否有路径,走过的不能重复走.

比如这个字符矩阵,我们找是否有BFCE这个字符串的路径.
恒明显有:

2.所有字符当为起点

传的一个指针来接受我们的二维数组.因为我们走过的不能重复的判断,所以我们我们做了一个bool类型的矩阵和二维数组完全对应.

我们遍历每一个矩阵的点来作为起点,看能不能走通,不能走通就返回false.

3.能否走通路径★

我们传入的参数有矩阵,行,列,某个点的行列,字符串,pathLength是字符匹配到第几个了.
visited是记录是否访问过的二维矩阵.

bool hasPathCore(const char* matrix, int rows, int cols, int row,int col, const char* str, int& pathLength, bool* visited)
{if (str[pathLength] == '\0'){return true;}bool hasPath = false;if (row >= 0 && row < rows && col >= 0 && col < cols&& matrix[row * cols + col] == str[pathLength]&& !visited[row * cols + col]){pathLength++;visited[row * cols + col] = true;hasPath = hasPathCore(matrix, rows, cols, row, col - 1,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row - 1, col,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row, col + 1,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row + 1, col,str, pathLength, visited);if (!hasPath){--pathLength;visited[row * cols + col] = false;}}return hasPath;
}

因为字符串的结尾是’\0’,如果都匹配到这里了,那么说明,我们的字符串就找完了,有路径,返回true,也是递归的结束条件.

判断这个点是否在矩阵范围内,是不是还没有访问,值是不是我们需要的字符.
是的话,就说明匹配成功了,我们就修改pathLength加+下次匹配下一个字符,同时改成已经访问过了.
然后我们递归的去放这个点的上下左右看有没有匹配到第二个字符的,若有继续递归,直到字符串结束符.

如上下左右都没有,我们就需要回退,同时将这个pathLength减1.并设置为未访问有可能其他路径能访问这里.

假如就像这种情况,我们是先判断的左上右下,那么我们就会先走左边F,然后又匹配到C,C很明显就匹配不到E了,所以我们需要回退,回退的时候,我们要将比对的字符也回比上一个,同时将这些改成为为访问,有可能别的路径会访问到这里.

4.单元测试

三.完整代码

#include <stdio.h>
#include <string>using namespace std;bool hasPathCore(const char* matrix, int rows, int cols, int row, int col,const char* str, int& pathLength, bool* visited);bool hasPath(const char* matrix, int rows, int cols, const char* str)
{if (matrix == NULL || rows < 1 || cols < 1 || str == NULL){return false;}bool* visited = new bool[rows * cols];memset(visited, 0, rows * cols);int pathLength = 0;for (int row = 0; row < rows; row++){for (int col = 0; col < cols; col++){if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited)){return true;}}}delete[]visited;return false;
}bool hasPathCore(const char* matrix, int rows, int cols, int row,int col, const char* str, int& pathLength, bool* visited)
{if (str[pathLength] == '\0'){return true;}bool hasPath = false;if (row >= 0 && row < rows && col >= 0 && col < cols&& matrix[row * cols + col] == str[pathLength]&& !visited[row * cols + col]){pathLength++;visited[row * cols + col] = true;hasPath = hasPathCore(matrix, rows, cols, row, col - 1,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row - 1, col,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row, col + 1,str, pathLength, visited)|| hasPathCore(matrix, rows, cols, row + 1, col,str, pathLength, visited);if (!hasPath){--pathLength;visited[row * cols + col] = false;}}return hasPath;
}//单元测试
void Test(const char* testName, const char* matrix, int rows, int cols,const char* str, bool expected)
{if (testName != NULL){printf("%s begins:", testName);}if (hasPath(matrix, rows, cols, str) == expected){printf("Passed.\n");}else{printf("FAILED.\n");}
}//ABTG
//CFCS
//JDEH//BFCEvoid Test1()
{const char* matrix = "ABTGCFCSJDEH";const char* str = "BFCE";Test("功能测试 1", matrix, 3, 4, str, true);
}//ABCE
//SFCS
//ADEE//SEE
void Test2()
{const char* matrix = "ABCESFCSADEE";const char* str = "SEE";Test("功能测试 2", matrix, 3, 4, str, true);
}//ABTG
//CFCS
//JDEH//ABFB
void Test3()
{const char* matrix = "ABTGCFCSJDEH";const char* str = "ABFB";Test("功能测试 3", matrix, 3, 4, str, false);
}//ABCEHJIG
//SFCSLOPQ
//ADEEMNOE
//ADIDEJFM
//VCEIFGGS//SLHECCEIDEJFGGFIE
void Test4()
{const char* matrix = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS";const char* str = "SLHECCEIDEJFGGFIE";Test("功能测试 4", matrix, 5, 8, str, true);
}//AAAA
//AAAA
//AAAA//AAAAAAAAAAAAvoid Test5()
{const char* matrix = "AAAAAAAAAAAA";const char* str = "AAAAAAAAAAAA";Test("边界值测试 5", matrix, 3, 4, str, true);
}//AAAA
//AAAA
//AAAA//AAAAAAAAAAAAAvoid Test6()
{const char* matrix = "AAAAAAAAAAAA";const char* str = "AAAAAAAAAAAAA";Test("边界值测试 6", matrix, 3, 4, str, false);
}//A//A
void Test7()
{const char* matrix = "A";const char* str = "A";Test("边界值测试 6", matrix, 1, 1, str, true);
}
//A//B
void Test8()
{const char* matrix = "A";const char* str = "B";Test("边界值测试 8", matrix, 1, 1, str, false);
}void Test9()
{Test("特殊情况测试 9", NULL, 0, 0, NULL, false);
}int main()
{Test1();Test2();Test3();Test4();Test5();Test6();Test7();Test8();Test9();system("pause");return 0;
}

运行结果:

单元测试的目标就是检测各种情况是否符合自己的预期,特别是要注意边界值!

2024年8月17日16:12:57