题解 | #矩阵中的路径#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public bool hasPath (List<List<char>> matrix, string word) {
        // write code here
        if(matrix.Count == 0)
            return false;
        
        int row = matrix.Count;
        int col = matrix[0].Count;
        List<List<bool>> gridCover = new List<List<bool>>(row);
        for(int i=0;i<row;i++){
            gridCover.Add(new List<bool>(col));
            for(int j=0;j<col;j++){
                gridCover[i].Add(false);
            }
        }
        
        for(int i=0; i<row; i++){
            for(int j=0;j<col;j++){
                if(step(matrix, word, gridCover, i, j, 1)){
                    return true;
                }
            }
        }
        return false;
    }
    
    public bool step(List<List<char>> matrix, string word, List<List<bool>> gridCover, int x, int y, int length){
        if(0 <= x && x < matrix.Count && 0 <= y && y < matrix[0].Count && !gridCover[x][y] && matrix[x][y] == word[length-1]){
            gridCover[x][y] = true;
            if (length == word.Length){
                return true;
            }else if (step(matrix, word, gridCover, x-1, y, length+1)
                || step(matrix, word, gridCover, x+1, y, length+1)
                || step(matrix, word, gridCover, x, y-1, length+1)
                || step(matrix, word, gridCover, x, y+1, length+1)){
                return true;
            }else{
                gridCover[x][y] = false;
                return false;
            }
        }
        return false;
    }
}