Implement 2D word search variants and analyze complexity

Given an m x n grid of uppercase letters board and a string word, implement two related functions: (

1. Fixed-direction search: Return true if word appears by choosing any start cell and moving in exactly one of eight directions (N, NE, E, SE, S, SW, W, NW), advancing one cell per step without changing direction or leaving bounds. Analyze time and space complexity, and explain how to avoid redundant checks. (
2. Flexible-path search: Return true if word can be formed by starting at any cell and moving to one of four orthogonal neighbors (up, down, left, right) at each step; you may change direction between steps but may not reuse a cell within a single path. Describe your algorithm (e.g., DFS/backtracking with pruning), its complexity, and key differences versus the fixed-direction variant. Specify how you would handle edge cases such as empty word, single-character inputs, repeated letters, and large grids.