1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
func maxWordPacking(board [][]byte, dictionary []string) int {
if len(board) == 0 || len(dictionary) == 0 {
return 0
}
dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
rows, cols := len(board), len(board[0])
maxWords := 0
var dfs func(word string, idx, r, c int, visited [][]bool, path *[][]int) bool
dfs = func(word string, idx, r, c int, visited [][]bool, path *[][]int) bool {
if idx == len(word) {
return true
}
if r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || board[r][c] != word[idx] {
return false
}
visited[r][c] = true
*path = append(*path, []int{r, c})
for _, dir := range dirs {
if dfs(word, idx+1, r+dir[0], c+dir[1], visited, path) {
return true
}
}
visited[r][c] = false
*path = (*path)[:len(*path)-1]
return false
}
findWordPaths := func(word string) [][][]int {
var allPaths [][][]int
visited := make([][]bool, rows)
for i := range visited {
visited[i] = make([]bool, cols)
}
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
path := [][]int{}
if dfs(word, 0, i, j, visited, &path) {
allPaths = append(allPaths, append([][][]int{}, path...))
// Reset visited
for _, cell := range path {
visited[cell[0]][cell[1]] = false
}
}
}
}
return allPaths
}
var backtrack func(idx int, used [][]bool, count int)
backtrack = func(idx int, used [][]bool, count int) {
if count > maxWords {
maxWords = count
}
for i := idx; i < len(dictionary); i++ {
paths := findWordPaths(dictionary[i])
for _, path := range paths {
canUse := true
for _, cell := range path {
if used[cell[0]][cell[1]] {
canUse = false
break
}
}
if canUse {
// Mark cells as used
for _, cell := range path {
used[cell[0]][cell[1]] = true
}
backtrack(i+1, used, count+1)
// Backtrack
for _, cell := range path {
used[cell[0]][cell[1]] = false
}
}
}
}
}
used := make([][]bool, rows)
for i := range used {
used[i] = make([]bool, cols)
}
backtrack(0, used, 0)
return maxWords
}
|