#include <stdio.h>
#include <string.h>
bool hasPathCore( char* A, int rows, int cols, int row, int col, char* str, int& pathLen, bool* visited);
bool hasPath(char* A, int rows, int cols, char* str)
{
if(A == NULL || rows < 1 || cols < 1 || str == NULL)
return false;
bool *visited = new bool[rows * cols];
memset(visited, 0, rows * cols);
int pathLen = 0;
for(int row = 0; row < rows; ++row)
for(int col = 0; col < cols; ++col)
if(hasPathCore(A, rows, cols, row, col, str,pathLen, visited))
return true;
delete[] visited;
return false;
}
bool hasPathCore( char* A, int rows, int cols, int row, int col, char* str, int& pathLen, bool* visited)
{
if(str[pathLen] == '\0')
return true;
bool hasPath = false;
if(row >= 0 && row < rows && col >= 0 && col < cols && A[row * cols + col] == str[pathLen]&&!visited[row * cols + col])
{
++pathLen;
visited[row * cols + col] = true;
hasPath = hasPathCore(A, rows, cols, row, col - 1, str, pathLen, visited)
|| hasPathCore(A, rows, cols, row, col + 1, str, pathLen, visited)
|| hasPathCore(A, rows, cols, row - 1, col, str, pathLen, visited)
|| hasPathCore(A, rows, cols, row + 1, col, str, pathLen, visited);
if(!hasPath)
{
--pathLen;
visited[row * cols + col] = false;
}
}
return hasPath;
}
int main()
{
char A[3][4]={'a','b','t','g','c','f','c','s','j','d','e','h'};
for(int i=0;i<3;++i)
{
for(int j=0;j<4;++j)
printf("%c ",A[i][j]);
printf("\n");
}
char *string="bfce";
char *String="abfb";
if(hasPath((char *)A, 3, 4, string))
printf("\n矩阵中存在路径:%s!\n",string);
else
printf("矩阵中不存此路径%s，或异常退出!\n",string);
if(hasPath((char *)A, 3, 4, String))
printf("\n矩阵中存在路径:%s!\n",String);
else
printf("矩阵中不存在路径:%s,或异常退出!\n",String);
return 0;
}
