golang力扣leetcode 79.单词搜索

type pair struct {
  x, y int
}
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func exist(board [][]byte, word string) bool {
  flag := false
  vis := make(map[pair]bool)
  n, m := len(board), len(board[0])
  var dfs func(x, y, idx int)
  dfs = func(x, y, idx int) {
    if word[idx] != board[x][y] {
      return
    }
    if idx == len(word)-1 {
      flag = true
      return
    }
    vis[pair{x, y}] = true
    for _, v := range dirs {
      nx, ny := x+v.x, y+v.y
      if nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[pair{nx, ny}] {
        dfs(nx, ny, idx+1)
      }
    }
    vis[pair{x, y}] = false
  }
  for i, v := range board {
    for j := range v {
      dfs(i, j, 0)
      if flag {
        return flag
      }
    }
  }
  return flag
}