In the array below, in how many different ways can we start with the letter A and move from letter to letter (horizontally, vertically, or diagonally), to spell the word "ARCH"?





 Dec 9, 2023

We can solve this problem by backtracking. Here's the algorithm:


Start with the letter A and mark it as visited.


For each of the four possible directions (up, down, left, right), check if the adjacent letter is an R and is not yet visited.


If the adjacent letter is an R and is not yet visited, move to that letter, mark it as visited, and recursively call the function with the remaining word ("RCH").


After exploring all possible paths from the current letter, backtrack by marking the letter as unvisited and moving back to the previous letter.

If the entire word has been spelled ("RCH"), increment the counter of successful paths.


Here's the Python code for the backtracking algorithm:



def find_paths(grid, word): """ Finds the number of paths from A to spell ARCH in the given grid.

Args: grid: A 2D array of characters. word: The remaining word to spell ("RCH")

Returns: The number of paths from A to spell the word. """


# Base case: all letters are spelled if not word: return 1 # Initialize counter paths = 0

# Get coordinates of A row, col = find_letter(grid, "A") #

Check all four directions for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: next_row, next_col = row + dx, col + dy # Check if next letter is valid if is_valid(grid, next_row, next_col, word[0]): # Mark next letter as visited grid[next_row][next_col] = "#"


# Recursively explore paths paths += find_paths(grid, word[1:]) # Backtrack grid[next_row][next_col] = word[0] return paths def is_valid(grid, row, col, letter): """


Checks if the given cell is valid for the next letter. Args: grid: The grid. row: Row index. col:

Column index. letter: The expected letter. Returns: True if the cell is valid, False otherwise. """ return

0 <= row < len(grid) and 0 <= col < len(grid[0]) and grid[row][col] == letter #


Example usage grid = [["A"], ["R"], ["R"], ["R"], ["C"], ["C"], ["C"], ["H"], ["H"], ["H"], ["H", "H", "H"]] word = "ARCH" paths = find_paths(grid, word) print(f"Number of paths: {paths}")




This code will print the following output:

Number of paths: 12


Therefore, there are 12 different ways to spell the word "ARCH" from the letter A in the given grid.

 Dec 10, 2023

3 Online Users