You are given an infinite supply of bricks. Each brick has one of two possible lengths: 2 units or 3 units.
Your task is to build a wall of a specified width and height.
The wall must be made up of horizontal rows of bricks. However, the bricks must be arranged so that the right edge of a brick in one row does not align vertically with the right edge of a brick in the row directly above or below it. This is to ensure the wall’s stability.
Write a Python function that takes two arguments: the width and the height of the wall. The function should return the count of all possible ways to build the wall that meet the criteria.
For example, if the width is 5 and the height is 1, there are 2 possible walls: (2,3) and (3,2). A wall with identical row patterns stacked on top of each other is not allowed.
If it is not possible to build the wall with the given width and height, return 0.
This problem is a classic state-compression counting task. First generate all valid row patterns for the given width using bricks of length 2 and 3, and record the internal crack positions of each pattern. Then use dynamic programming to count how many ways to stack rows of the required height so that adjacent rows never share a crack at the same vertical position. The core idea is to model each row as a state and transition only between compatible states. If the width cannot be formed by any combination of 2 and 3, the answer is 0.
