<p>You are given an <code>m x n</code> matrix <code>board</code>, representing the<strong> current </strong>state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), <code>&#39; &#39;</code> to represent any <strong>empty </strong>cells, and <code>&#39;#&#39;</code> to represent any <strong>blocked</strong> cells.</p>

<p>A word can be placed<strong> horizontally</strong> (left to right <strong>or</strong> right to left) or <strong>vertically</strong> (top to bottom <strong>or</strong> bottom to top) in the board if:</p>

<ul>
	<li>It does not occupy a cell containing the character <code>&#39;#&#39;</code>.</li>
	<li>The cell each letter is placed in must either be <code>&#39; &#39;</code> (empty) or <strong>match</strong> the letter already on the <code>board</code>.</li>
	<li>There must not be any empty cells <code>&#39; &#39;</code> or other lowercase letters <strong>directly left or right</strong><strong> </strong>of the word if the word was placed <strong>horizontally</strong>.</li>
	<li>There must not be any empty cells <code>&#39; &#39;</code> or other lowercase letters <strong>directly above or below</strong> the word if the word was placed <strong>vertically</strong>.</li>
</ul>

<p>Given a string <code>word</code>, return <code>true</code><em> if </em><code>word</code><em> can be placed in </em><code>board</code><em>, or </em><code>false</code><em> <strong>otherwise</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/04/crossword-ex1-1.png" style="width: 478px; height: 180px;" />
<pre>
<strong>Input:</strong> board = [[&quot;#&quot;, &quot; &quot;, &quot;#&quot;], [&quot; &quot;, &quot; &quot;, &quot;#&quot;], [&quot;#&quot;, &quot;c&quot;, &quot; &quot;]], word = &quot;abc&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> The word &quot;abc&quot; can be placed as shown above (top to bottom).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/04/crossword-ex2-1.png" style="width: 180px; height: 180px;" />
<pre>
<strong>Input:</strong> board = [[&quot; &quot;, &quot;#&quot;, &quot;a&quot;], [&quot; &quot;, &quot;#&quot;, &quot;c&quot;], [&quot; &quot;, &quot;#&quot;, &quot;a&quot;]], word = &quot;ac&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to place the word because there will always be a space/letter above or below it.</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/04/crossword-ex3-1.png" style="width: 478px; height: 180px;" />
<pre>
<strong>Input:</strong> board = [[&quot;#&quot;, &quot; &quot;, &quot;#&quot;], [&quot; &quot;, &quot; &quot;, &quot;#&quot;], [&quot;#&quot;, &quot; &quot;, &quot;c&quot;]], word = &quot;ca&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> The word &quot;ca&quot; can be placed as shown above (right to left). 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 &lt;= m * n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>board[i][j]</code> will be <code>&#39; &#39;</code>, <code>&#39;#&#39;</code>, or a lowercase English letter.</li>
	<li><code>1 &lt;= word.length &lt;= max(m, n)</code></li>
	<li><code>word</code> will contain only lowercase English letters.</li>
</ul>

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        # Get the dimensions of the board
        M, N = len(board), len(board[0])
        word_length = len(word)
        # Possible directions to place the word: down, right, up, left
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        def can_place(row, col, delta_row, delta_col):
            """ Check if the word can be placed starting from (row, col) in the specified direction """
            
            # Check if there's an invalid cell before the starting position
            # Calculate the coordinates of the cell immediately before the starting point (row, col)
            # in the specified direction (delta_row, delta_col).
            # This is to ensure the placement of the word is isolated and valid.
            start_boundary_row, start_boundary_col = row - delta_row, col - delta_col

            # Check if the start boundary cell is within the bounds of the board and not blocked.
            # This ensures that there is no open space or part of another word immediately before the starting point.
            # If the start boundary cell is within bounds and not blocked, the current starting point is invalid.
            if 0 <= start_boundary_row < M and 0 <= start_boundary_col < N and board[start_boundary_row][start_boundary_col] != '#':
                return False
                # Diagram:
                #   |#| (start boundary cell, must be blocked)
                #   | | (start cell)
                # Example: If placing 'word' vertically downwards at (1, 1), cell (0, 1) must be blocked or out of bounds

                # Detailed Explanation:
                #
                # - The condition `0 <= start_boundary_row < M` checks if the start boundary row index is within the valid range.
                # - The condition `0 <= start_boundary_col < N` checks if the start boundary column index is within the valid range.
                # - The condition `board[start_boundary_row][start_boundary_col] != '#'` checks if the start boundary cell is not blocked.
                #   If all these conditions are true, it means the start boundary cell is an open space within the board.
                #   This violates the requirement that the word should be placed in an isolated space, bounded by blocks or edges.
                #
                # Diagram:
                #   Assume we have a 5x5 board:
                #   [
                #     [' ', ' ', '#', ' ', ' '],
                #     [' ', ' ', ' ', ' ', ' '],
                #     [' ', ' ', ' ', ' ', ' '],
                #     [' ', ' ', ' ', ' ', ' '],
                #     [' ', ' ', ' ', ' ', ' ']
                #   ]
                #
                #   Suppose `row = 2`, `col = 2`, and the direction is `(0, 1)` (right).
                #   Calculating start boundary:
                #     start_boundary_row = 2 - 0 = 2
                #     start_boundary_col = 2 - 1 = 1
                #
                #   The cell before (2, 2) in the right direction is (2, 1).
                #   Check if (2, 1) is within the board and not blocked:
                #     0 <= 2 < 5 and 0 <= 1 < 5 and board[2][1] != '#'
                #
                #   Since (2, 1) is within bounds and not blocked, the function would return `False` if this cell is open.
                #   This ensures that the word placement does not start in an invalid location where there is an open space or another
                #   word right before it, maintaining the crossword's proper structure and rules.

            
            # Iterate over the length of the word to check each position
            # Detailed Explanation:
            #
            # - The function iterates over each cell (r, c) in the board.
            # - It skips cells that are blocked (board[r][c] == '#').
            # - For each non-blocked cell, it checks all four possible directions (down, right, up, left).
            # - If the helper function `can_place` returns True for any direction, it means the word can be placed starting from that cell.
            # - The function returns True if a valid placement is found.
            # - If no valid placement is found after checking all cells and directions, the function returns False.
            #
            # Diagrams and Examples:
            #
            # Assume we have a 5x5 board:
            # [
            #   [' ', ' ', '#', ' ', ' '],
            #   [' ', ' ', ' ', ' ', ' '],
            #   [' ', ' ', ' ', ' ', ' '],
            #   [' ', ' ', ' ', ' ', ' '],
            #   [' ', ' ', ' ', ' ', ' ']
            # ]
            #
            # Suppose the word is 'word'.
            #
            # Example of placing 'word' horizontally starting at (1, 1):
            #   - Check direction (0, 1) (right):
            #     - Start boundary: (1, 0)
            #     - Check each cell in the word's length: (1, 1), (1, 2), (1, 3), (1, 4)
            #     - End boundary: (1, 5)
            #
            #   The start boundary cell (1, 0) is checked to ensure it is either out of bounds or blocked.
            #   Each cell in the path is checked to ensure it matches the word character or is empty.
            #   The end boundary cell (1, 5) is checked to ensure it is either out of bounds or blocked.
            #
            # If all conditions are met, the word 'word' can be placed starting at (1, 1) in the right direction.
            #
            # Similarly, the function checks other directions (down, up, left) for all valid starting points.
            for i in range(word_length):
                # Check if current cell is out of bounds, blocked, or doesn't match the word
                if not (0 <= row < M and 0 <= col < N) or board[row][col] == '#' or (board[row][col] != ' ' and board[row][col] != word[i]):
                    return False
                    # Diagram:
                    #   Current position -> |w| (word character)
                    #   Board cell -> | | or |w| (must match or be empty)
                    # Example: Placing 'word' horizontally at (1,1):
                    #   - | | |#| |
                    #   - |w|o|r|d|
                
                # Move to the next cell in the specified direction
                row += delta_row
                col += delta_col
            
            # Check if there's an invalid cell after the ending position
            if 0 <= row < M and 0 <= col < N and board[row][col] != '#':
                return False
                # Diagram:
                #   | | (end cell)
                #   |#| (end boundary cell, must be blocked)
                # Example: After placing 'word' horizontally at (1,1), cell (1,5) must be blocked or out of bounds
            
            return True

        # Iterate over each cell in the board to check possible starting points
        for r in range(M):
            for c in range(N):
                # Skip blocked cells
                if board[r][c] == '#':
                    continue
                # Check all possible directions from the current cell
                for delta_row, delta_col in directions:
                    if can_place(r, c, delta_row, delta_col):
                        return True
                        # Diagram:
                        # Checking direction (1,0) from (1,1)
                        #   | | (start) 
                        #   |w| (next cell, word character match)
                        #   |o| (next cell, word character match)
                        #   ...
        
        return False  # No valid placement found


# Usage example:
board = [
    [" ", "#", "a"],
    [" ", "#", "c"],
    [" ", "#", "a"]
]
word = "ac"
print(Solution().placeWordInCrossword(board, word))  # Output: False, as explained in the examples and diagrams.


1266