package main

func hasPath(matrix [][]byte, word string) bool {
	// write code here
	row := len(matrix)
	col := len(matrix[0])
	strLen := len(word)
	if row == 0 || col == 0 || strLen == 0 {
		return false
	}
	isVisited := make([][]bool, row)
	for k := 0; k < row; k++ {
		isVisited[k] = make([]bool, col)
	}
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if matrix[i][j] == word[0] {
				if dfs(row, col, strLen, i, j, 0, word, matrix, isVisited) {
					return true
				}
			}
		}
	}
	return false
}

func dfs(row int, col int, strLen int, i int, j int, count int, word string, matrix [][]byte, isVisited [][]bool) bool {
	if i < 0 || j < 0 || i >= row || j >= col || isVisited[i][j] || matrix[i][j] != word[count] {
		return false
	}

	if count == strLen-1 {
		return true
	}

	isVisited[i][j] = true
	if dfs(row, col, strLen, i-1, j, count+1, word, matrix, isVisited) ||
		dfs(row, col, strLen, i+1, j, count+1, word, matrix, isVisited) ||
		dfs(row, col, strLen, i, j-1, count+1, word, matrix, isVisited) ||
		dfs(row, col, strLen, i, j+1, count+1, word, matrix, isVisited) {
		return true
	} else {
		isVisited[i][j] = false
		return false
	}

}