矩陣中的路徑

02-12

矩陣中的路徑

回溯法經典題
判斷在一個矩陣中是否存在一條包含某個字元串中所有字元的路徑。

參考代碼：

#include <stdio.h>#include <string.h>#include <stdlib.h>int core(char* matrix,int rows,int cols,int row,int col,char* str,int* pathLen,int* visited){ int hasPath = 0; if(str[*pathLen] == ) hasPath = 1; if(row >= 0 && row <rows && col > 0 && col < cols && matrix[row * cols + col] == str[*pathLen] && !visited[row * cols + col]) { ++(*pathLen); visited[row * cols + col] = 1; hasPath = core(matrix,rows,cols,row,col-1,str,pathLen,visited) || core(matrix,rows,cols,row,col+1,str,pathLen,visited) || core(matrix,rows,cols,row-1,col,str,pathLen,visited) || core(matrix,rows,cols,row+1,col,str,pathLen,visited); if(!hasPath) { --(*pathLen); visited[row * cols + col] = 0; } } return hasPath;}int hasPath(char* matrix,int rows,int cols,char* str){ int res = 0; if(matrix == NULL || rows < 1 || cols < 1 || str == NULL) return res; int* visited = (int*) malloc((rows * cols)*sizeof(int)); memset(visited,0,(rows * cols)*sizeof(int)); int pathLen = 0; for(int row = 0;row < rows;++row) { for(int col = 0;col < cols;++col) { if(core(matrix,rows,cols,row,col,str,&pathLen,visited)) { res = 1; return res; } } } free(visited); return res;}int main(){ char* matrix = "abtgcfcsjdeh"; char* str = "bfce"; int rows = 3; int cols = 4; int res = hasPath(matrix,rows,cols,str); printf("%d ",res); return 0;}