package main

// Pos stands for the position of board[y][x]
type Pos struct {
	x int
	y int
}

func existIter(board [][]byte, word string, visited map[Pos]struct{}, last Pos) bool {
	if _, ok := visited[last]; ok {
		return false
	}
	if len(word) == 0 {
		return true
	}
	visited[last] = struct{}{}
	for dir := 0; dir < 4; dir++ {
		var pos Pos
		switch dir {
		case 0: // up
			if last.y > 0 && board[last.y-1][last.x] == word[0] {
				pos = Pos{last.x, last.y - 1}
			} else {
				continue
			}
		case 1: // down
			if last.y < len(board)-1 && board[last.y+1][last.x] == word[0] {
				pos = Pos{last.x, last.y + 1}
			} else {
				continue
			}
		case 2: // left
			if last.x > 0 && board[last.y][last.x-1] == word[0] {
				pos = Pos{last.x - 1, last.y}
			} else {
				continue
			}
		default: // right
			if last.x < len(board[0])-1 && board[last.y][last.x+1] == word[0] {
				pos = Pos{last.x + 1, last.y}
			} else {
				return false
			}
		}
		newMap := make(map[Pos]struct{})
		for k := range visited {
			newMap[k] = struct{}{}
		}
		if existIter(board, word[1:], newMap, pos) {
			return true
		}
	}
	return false
}

// too complex and slow
func existOld(board [][]byte, word string) bool {
	beg := word[0]
	for y, row := range board {
		for x, v := range row {
			if beg == v && existIter(board, word[1:], map[Pos]struct{}{}, Pos{x, y}) {
				return true
			}
		}
	}
	return false
}

func exist(board [][]byte, word string) bool {
	return false
}

/* func main() {
	b1 := [][]byte{
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'C', 'S'},
		{'A', 'D', 'E', 'E'},
	}
	fmt.Println(exist(b1, "ABCCED"))
	fmt.Println(exist(b1, "SEE"))
	fmt.Println(exist(b1, "ABCB"))
	fmt.Println(exist(b1, "FSADEESCCBA"))
	fmt.Println(exist(b1, "ZSADEESCCBA"))
} */