## 一、题目

a b c e s f c s a d e e

## 三、解题代码

``````public class Test {
/**
* 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
* 路径可以从矩阵中任意一格开始，每一步可以在矩阵中间向左、右、上、下移动一格。
* 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
*
* @param matrix 输入矩阵
* @param rows   矩阵行数
* @param cols   矩阵列数
* @param str    要搜索的字符串
* @return 是否找到 true是，false否
*/
public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
// 参数校验
if (matrix == null || matrix.length != rows * cols || str == null || str.length < 1) {
return false;
}

// 变量初始化
boolean[] visited = new boolean[rows * cols];
for (int i = 0; i < visited.length; i++) {
visited[i] = false;
}

// 记录结果的数组，
int[] pathLength = {0};
// 以每一个点为起始进行搜索
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (hasPathCore(matrix, rows, cols, str, visited, i, j, pathLength)) {
return true;
}
}
}

return false;
}

/**
* 回溯搜索算法
*
* @param matrix     输入矩阵
* @param rows       矩阵行数
* @param cols       矩阵列数
* @param str        要搜索的字符串
* @param visited    访问标记数组
* @param row        当前处理的行号
* @param col        当前处理的列号
* @param pathLength 已经处理的str中字符个数
* @return 是否找到 true是，false否
*/
private static boolean hasPathCore(char[] matrix, int rows, int cols, char[] str, boolean[] visited,
int row, int col, int[] pathLength) {

if (pathLength == str.length) {
return true;
}

boolean hasPath = false;

// 判断位置是否合法
if (row >= 0 && row < rows
&& col >= 0 && col < cols
&& matrix[row * cols + col] == str[pathLength]
&& !visited[row * cols + col]) {

visited[row * cols + col] = true;
pathLength++;

// 按左上右下进行回溯
hasPath = hasPathCore(matrix, rows, cols, str, visited, row, col - 1, pathLength)
|| hasPathCore(matrix, rows, cols, str, visited, row - 1, col, pathLength)
|| hasPathCore(matrix, rows, cols, str, visited, row, col + 1, pathLength)
|| hasPathCore(matrix, rows, cols, str, visited, row + 1, col, pathLength);

if (!hasPath) {
pathLength--;
visited[row * cols + col] = false;
}

}

return hasPath;
}
}``````
{"ft_lang_label":"__label__zh","ft_lang_prob":0.60805136,"math_prob":0.99263424,"size":2618,"snap":"2019-13-2019-22","text_gpt3_token_len":1408,"char_repetition_ratio":0.16182096,"word_repetition_ratio":0.1845238,"special_character_ratio":0.2987013,"punctuation_ratio":0.19315404,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9500571,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-05-19T23:14:46Z\",\"WARC-Record-ID\":\"<urn:uuid:e8652e3e-4270-4537-b431-c6e885b3e356>\",\"Content-Length\":\"44871\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4e535f48-2101-46b5-8118-2211c1b4cae0>\",\"WARC-Concurrent-To\":\"<urn:uuid:eb014ce1-7235-42d7-8057-138924eb170f>\",\"WARC-IP-Address\":\"121.40.159.191\",\"WARC-Target-URI\":\"http://androidos.net.cn/codebook/AndroidRoad/algorithm/For-offer/63.html\",\"WARC-Payload-Digest\":\"sha1:AP5Q62OEPXZ7VAHI5C4RWFYQBDAAEXE4\",\"WARC-Block-Digest\":\"sha1:TMLHELNAS36AEZ5OBSECIVE5HYFUXSRC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-22/CC-MAIN-2019-22_segments_1558232255182.37_warc_CC-MAIN-20190519221616-20190520003616-00067.warc.gz\"}"}