/*

题目：

	设计一个函数，判断一个矩阵中是否存在一条包含该字符串所有字符的路径。

	路径可从字符串的任意一格开始，每一步可向上、下、左、右移动一格。

	如果一条路径经过了矩阵中的某一格，那么该路径不能再次经过该格。

*/

/*

思路：

	采用回溯法。

	遍历数组，当选中其中一个格子时，若与当前字符串的指定位置匹配，

	则检测它四周的格子是否匹配，若匹配，继续深入，不匹配，则回退一格。

*/

#include <iostream>

#include<vector>

#include<string.h>

using namespace std;

bool hasPathCore(const char* matrix,int rows,int cols,int row,int col,const char* str,int& lengthAt,bool* visited){

    if(str[lengthAt] == '\0') return true;

    if(row >=0 && col >=0 && row < rows && col < cols && !visited[cols*row+col] &&matrix[row*cols+ col] == str[lengthAt]){

        visited[row*cols+ col] = true;

        lengthAt++;

        cout<<" "<<matrix[row*cols+col];

        if(hasPathCore(matrix,rows,cols,row+1,col,str,lengthAt,visited) || hasPathCore(matrix,rows,cols,row-1,col,str,lengthAt,visited) ||

           hasPathCore(matrix,rows,cols,row,col+1,str,lengthAt,visited) || hasPathCore(matrix,rows,cols,row,col-1,str,lengthAt,visited) ) {

            return true;

           }

        --lengthAt;

        visited[row*cols+col] = false;

    }

    return false;

}

bool hasPath(char* matrix,int rows,int cols,char* str){

    if(!matrix || rows <= 0 || cols <= 0 || !str){

        return false;

    }

    bool* visited = new bool[rows*cols];

    memset(visited,0,rows*cols);

    int lengthAt = 0;

    for(int row = 0; row < rows; row++){

        for(int col = 0; col < cols; col++){

            cout<<row<<" "<<col<<endl;

            cout<<matrix[cols*row + col]<<" ";

            if(hasPathCore(matrix,rows,cols,row,col,str,lengthAt,visited)){

                return true;

            }

            cout<<endl;

        }

    }

    return false;

}

int main()

{

    char matrix[] = "ABCEHJIG SFCSLOPQ ADEEMNOE ADIDEJFM VCEIFGGS";

    //char* matrix = "abtgcfcsjdeh";

    char str[] = "SGGFIECVAASABCEHJIGQEM";

    cout<<hasPath(matrix,5,8,str);

    return 0;

}