Count blocks in a 2D grid

Question

Challenge description

Let's define an W x H grid as a two-dimensional array of length H whose each subarray is of length W. Example: a 2x3 grid (. character used as a blank):

..
..
..

A unit is a single point of a grid. A block is either a single unit or a set of contiguous units (meaning each unit of a block has at least another one next to, above or below it). In the 10x10 grid below there are 4 blocks (units represented by X's):

........X.   ........1.
..X.......   ..2.......
..X.......   ..2.......
..X.......   ..2.......
.......X..   .......3..
.......XX.   .......33.
.......XX.   .......33.
..X.......   ..4.......
..XX..X...   ..44..4...
...XXXX...   ...4444...

Two blocks are distinct if either their positions in the grid or the number of blocks they consist of are different. In the 10x10 grid below there are 5 blocks (they're all 2x2 squares, but their positions are different, therefore they're distinct):

..........   ..........
.XX....XX.   .11....22.
.XX....XX.   .11....22.
..........   ..........
.......XX.   .......33.
.......XX.   .......33.
....XX....   ....44....
....XX....   ....44....
XX........   55........
XX........   55........

Given two integers W and H (W, H > 0), calculate the number of distinct blocks that can be constructed within a W x H grid.

Sample inputs / outputs

(1, 1) -> 1     | only a 1x1 block can be constructed
(1, 2) -> 3     | two 1x1 blocks, and one 1x2 block
(2, 2) -> 13
(3, 3) -> 218
(4, 4) -> 11506

Notes

• Remember that this is a code-golf challenge, so make your code as short as possible!
• Relevant sequences: A059525, A059020

Answer 1

Python 2, 208 184 169 167 163 bytes

w,h=input()
def f(x):global g;o=g;g&=~2**x;o>g>[x/w==(x+s)/w<f(x+s)or-1<x/w+s<h<f(x+s*w)for s in[-1,1]]
n=i=1<<w*h
while i:g=i=i-1;f(len(bin(g))-3);n-=g>0
print~-n