Simulate fixed-shape tiling on a grid
Overview
This question evaluates a candidate's ability to implement grid-based simulation and pattern-matching algorithms, including handling fixed-shape placements, internal holes, bounds checking, collision detection, and explicit scanning/tie-breaking rules.
You are given an empty n-by-m grid and a list of tile patterns, patterns[0..k-1]. Each pattern is a binary matrix (1 = filled cell, 0 = hole) and must be placed exactly as given—no rotation or reflection. Starting with patterns[0], for each pattern i, scan the grid in row-major order (top to bottom, left to right) to find the top-left-most position where all 1-cells of the pattern fit entirely within bounds and only cover currently empty grid cells. If a valid position exists, place the pattern there and write the integer (i +
- into every covered cell; if no position exists, skip this pattern and continue. After processing all patterns, output the final grid as n rows and m columns, using '.' for cells that remain empty. Implement a function that performs this simulation. Clearly specify your scanning order, tie-breaking, and how you represent patterns. Discuss time and space complexity and edge cases (e.g., patterns with holes, patterns larger than the grid, overlapping attempts).