回溯之矩阵中是否存在某个字符串

题目

存在类似以下的矩阵，判断矩阵中是否存在某个字符串，比如存在 adeh，不存在 adhk

['a', 'b', 'c'
 'd', 'e', 'f'
 'g', 'h', 'i' 
 'j', 'k', 'l'
]

题解

穷举所有路径，找到就返回真，否则为假。矩阵中每个点都假设有上下左右四个选择，从起点开始遍历路径，遇到正确的就接着往下走，不正确的就回退到上一步。

object solution {

	val notions = Seq(Seq(0, 1), Seq(0, -1), Seq(1, 0), Seq(-1, 0))

	def adjust(array:Array[Array[String]], str:String) = {
		val row = array.length
		val col = array(0).length
		val marked = Array.ofDim[Boolean](row, col)

		if (row == 0 || col == 0 ){
			return false
		} else {
			def backtracking(marked:Array[Array[Boolean]], strLen:Int, r:Int, c:Int) :Boolean= {
				val str_ = str(strLen)
				if (r<0 || c<0 || c>col || r>row || marked(r)(c)==false || array(r)(c) != str_){
					return false
				}

				marked(r)(c) = true

				for(n <- notions) {
					if (backTracking(marked, sLen+1, r+n.head, c+n(1))) {
            			return true
          			}
				}
				marked(r)(c) = false
				false

			}
			for (i <- 0 until row) {
		        for (j <- 0 until col){
		          if (backTracking(marked, 0, i, j)){
		            return true
          			}
        		}

      		}
      		false
		}
	}

}