Number of valid mazes

Question

Given a WxH grid, how many possible mazes are there?

Things you know about the maze:

1. The grid is exactly H squares high and W squares wide.
2. There are three types of squares: Start, Finish, and Empty. Your maze must contain exactly 1 Start and 1 Finish, and all remaining squares are Empty.
3. There are walls surrounding the entire maze.
4. Walls can exist on the edge between any two squares, unless it breaks the below rule:
5. There must exist a path from the Start square to the Finish square.

Therefore, given two numbers, W and H, you must return a single number representing the number of possible square/wall configurations. You are guaranteed that W*H > 1

For example, the 2x2 maze has exactly 100 different possible configurations.

This is a code-golf so the shortest answer wins!

Answer 1

Python 2, 329 310 bytes

from itertools import*
w,h=input()
R=range(w*h)
p=product
n=0
Z=[(x,y)for x,y in p(R,R)if abs(x%w-y%w)+abs(x/w-y/w)<2]
for s,f,W in p(R,R,p(*[((),z)for z in Z if z[0]<z[1]])):
 V={s};C=[s];v=0
 while C:
  c=C.pop();v|=c==f!=s;V|={c}
  for o,q in Z:C+=(c==o)*len({q,(o,q),(q,o)}-(V|set(W)))/3*[q] 
 n+=v
print n

This is the golfed (and much more inefficient) version of the program I was using while discussing the problem with @Nathan. I can save a few bytes by replacing some space indents with tabs, but I'll save that for later.

The algorithm is simply generate every maze, then flood fill from the start, seeing if we pass the finish at some point or not.