6.15矩阵中的路径 - WisperDin/blog GitHub Wiki
面试题12：矩阵中的路径 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
A B T G
C F C S
J D E H
显而易见，此题目需要用到回溯去处理这种路径的问题，回溯可以通过递归，栈实现 处理步骤：
- 对矩阵中的每一个位置，都调用查找路径的函数，只要在一个位置查找到成功则返回成功
- 在查找路径函数中，先检查开始点是否匹配字符串第一个元素，不是则直接返回失败
- 利用栈+循环 当栈的长度与字符串长度相等时，即匹配完成，返回成功
- 考察当前位置的邻居，寻找与当前匹配中的字符符合的邻居位置，邻居位置入栈，更新当前位置到该位置，继续考察
- 当路径无法继续匹配下去且当前找到的字符序列未满足目标字符串时，回溯到上一个字符（弹出栈顶元素，重置当前位置到前一位置），继续寻找匹配的路径
根据题意，还需要标记访问过的格子，不允许重复访问
entrypoint - MatPath
package mat_path
import (
"container/list"
"fmt"
"strings"
"strconv"
"log"
)
func around(mat [][]byte,target byte, row,col int,visited map[string]bool) (int,int) {
if row > 0 && mat[row-1][col] == target&& !visited[fmt.Sprintf("%d-%d",row-1,col)] {
return row-1,col
}
if col > 0 && mat[row][col-1] == target && !visited[fmt.Sprintf("%d-%d",row,col-1)] {
return row,col-1
}
if row < len(mat)-1 && mat[row+1][col] == target && !visited[fmt.Sprintf("%d-%d",row+1,col)] {
return row+1,col
}
if col < len(mat[0])-1 && mat[row][col+1] == target && !visited[fmt.Sprintf("%d-%d",row,col+1)] {
return row,col+1
}
return -1,-1
}
var debugFlag = true
//chk path exist in a start point
func FindPath(mat [][]byte,row,col int,target string) bool {
stack := list.List{}
visited := make(map[string]bool)
//chk first ele
if target[0] != mat[row][col] {
return false
}
//push first ele to stack && set visited
key := fmt.Sprintf("%d-%d",row,col)
stack.PushFront(key)
visited[key] = true
for {
if debugFlag {
log.Println(string(mat[row][col]))
log.Println(fmt.Sprintf("%d-%d",row,col))
}
//chk if all correct
if stack.Len() == len(target) {
return true
}
//chk this position around get first ele match the next str
row,col = around(mat,target[stack.Len()],row,col,visited)
//find sth
if row!= -1 && col != -1 {
key = fmt.Sprintf("%d-%d",row,col)
stack.PushFront(key)
visited[key] = true
}else{
//find nothing
//only 1 ele in stack ,
if stack.Len()<=1 {
return false
}
//stack len >= 2
//backtracking!!!
//remove the front in the stack && reset the row , col to the previous ele
stack.Remove(stack.Front())
split := strings.Split(stack.Front().Value.(string),"-")
row,_ = strconv.Atoi(split[0])
col,_ = strconv.Atoi(split[1])
}
}
}
//chk path exist in mat
func MatPath(mat [][]byte, target string) bool {
if len(mat)<=0 || len(mat[0])<=0 || target ==""{
return false
}
for r:=0;r<len(mat) ;r++ {
for c:=0;c<len(mat[r]) ;c++ {
if FindPath(mat,r,c,target) {
return true
}
}
}
return false
}面试题13：机器人的运动范围 题目：地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动，它每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标数位之和大于k的格子。例如，当k为18时，机器人能够进入方格(35, 37)，因为3+5+3+7=18。但它不能进入方格(35, 38)，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
func MovingCount(k,m,n int) int {
if m <= 0 || n<=0 || k<=0 {
return 0
}
return movingCount(k,m,n,0,0,map[int]bool{})
}
func movingCount(k,m,n,row,col int,visited map[int]bool) int {
if m <= 0 || n<=0 || k<=0 {
return 0
}
if row<0 || col <0 || row>=m || col >= n ||
visited[row+col*n] ||
getDigitSum(row)+getDigitSum(col) > k{
return 0
}
visited[row+col*n] = true
return 1+
movingCount(k,m,n,row-1,col,visited)+
movingCount(k,m,n,row,col-1,visited)+
movingCount(k,m,n,row,col+1,visited)+
movingCount(k,m,n,row+1,col,visited)
}
func getDigitSum(n int) int {
if n<=0 {
return 0
}
sum := 0
for n>0 {
sum += n%10
n/=10
}
return sum
}