题解 | #矩阵中的路径#

class Solution {
public:
    /**
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        if (word.size() == 0) {
            return true;
        }

        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return false;
        }
        
        int height = matrix.size();
        int width = matrix[0].size();

        char* first = &word[0];
        // find positions whose char value equals the head of word
        vector<vector<int>>hasfirstPoss;
        for(int i = height - 1; i >= 0; --i){
            for (int j = width - 1; j >= 0; --j){
                if (matrix[i][j] == *first) {
                    vector<int> pos;
                    pos.push_back(i);
                    pos.push_back(j);
                    hasfirstPoss.push_back(pos);
                }
            }
        }

        for(int i = 0; i < hasfirstPoss.size(); i++) {
            if (hasPath(matrix, hasfirstPoss[i][0], hasfirstPoss[i][1], first)){
                return true;
            }
        }

        // if hasfirstPoss has no item or all items checks faild
        return false;
    }

    // find from specific position
    bool hasPath(vector<vector<char> >& matrix, int x, int y, char* word_char) {
        if ((word_char+1) == nullptr) {
            return true;
        }
        char* next_word = word_char + 1;
        
        if (*next_word == '\0') {
            return true;
        }

        int height = matrix.size();
        int width = matrix[0].size();

        for (int dx = -1; dx < 2; ++dx){
            for (int dy = -1; dy < 2; ++dy){
                if (dx == dy || dx*dy != 0) {
                    continue;
                }
                int nx = x + dx;
                int ny = y + dy;
                if (nx < 0 || ny < 0 || nx >= height || ny >= width) {
                    continue;
                }
                if (matrix[nx][ny] == *next_word) {
                    // make a copy
                    vector<vector<char> > matrix_copy;
                    for(int i = 0; i < height; ++i){
                        vector<char> line;
                        for (int j = 0; j < width; ++j){
                            line.push_back(matrix[i][j]);
                        }
                        matrix_copy.push_back(line);
                    }
                    // go back in not permitted;
                    matrix_copy[nx][ny] = '\0';

                    // to find the next char recursively
                    bool result = hasPath(matrix_copy, nx, ny, next_word);
                    if (result) {
                        return result;
                    }
                }
            }
        }
        return false;
    }
};