Company: Cisco_26dec
Difficulty: medium
Word Search in a Grid You're developing the core algorithm for a next-generation word puzzle game that combines elements of Scrabble and Boggle. The game is played on a large grid where players must find words from a massive dictionary, but with advanced scoring mechanics that require finding ALL possible words efficiently. Real-World Scenario: Your game engine needs to process thousands of concurrent games with grids up to 20x20 and dictionaries containing 100,000+ words. A naive solution that checks every possible path would create unacceptable server load and timeout issues. The Challenge: Given a 2D grid of characters and a dictionary, find ALL valid words that can be formed by connecting adjacent cells (8-directional movement). Each cell can only be used once per word path. Input Format The input should be read from standard input (stdin) in the following format: rows cols board (rows lines, each with cols space-separated characters) num_words dictionary (num_words lines, each con