題目描述
請設計一個函式，用來判斷在一個矩陣中是否存在一條包含某字串所有字符的路徑，路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子，如果一條路徑經過了矩陣中的某一個格子，則該路徑不能再進入該格子， 例如 a b c e s f c s a d e e 矩陣中包含一條字串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因為字串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入該格子， 思路：這題和機器人那題類似，只是出發點不再是（0，0）了，其他想法類似，代碼如下：class Solution {public: bool hasFun(char* matrix, int rows, int cols, char* str,int x,int y,bool * flags,int pos) { if(pos==strlen(str)) { return true; } if(x>=rows||y>=cols||x<0||y<0) return false; if(flags[x*cols+y]) return false; if(matrix[x*cols+y]==str[pos]) { flags[x*cols+y]=true; bool fc=hasFun(matrix,rows,cols,str,x-1,y,flags,pos+1)||hasFun(matrix,rows,cols,str,x+1,y,flags,pos+1)||hasFun(matrix,rows,cols,str,x,y-1,flags,pos+1)||hasFun(matrix,rows,cols,str,x,y+1,flags,pos+1); return fc; } else return false; } bool hasPath(char* matrix, int rows, int cols, char* str) { for(int x=0;x<rows;x++) { for(int y=0;y<cols;y++) { if(matrix[x*cols+y]==str[0]) { bool * flags=new bool[rows*cols]; for(int i=0;i<rows*cols;i++) { flags[i]=false; } if(hasFun(matrix,rows,cols,str,x,y,flags,0)) return true; } } } return false; }};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24582.html
標籤：其他
上一篇：機器人的運動范圍