What if tiles are larger than 1×2? Tetrominoes (1×4) or square tiles (2×2)? Larger tiles mean transitions look back multiple rows.
The profile might span 2 or more rows. State: represent the last k rows, where k is the tile height. State space grows to 2k⋅m. Practical limit: k⋅m≤20 or so. Beyond that, state space is too large. The profile depth equals the tile height. Larger tiles exponentially increase the state space.