A square grid of size $n\times m$ is given, where each tile can either be a floor tile or a wall tile.
One corner tile represents the entrance, and the opposite corner tile of that is called the exit.
These two tiles cannot be a wall tile and are classified as a floor tile.
A grid configuration is a valid maze if both properties hold:
Entrance and exit tiles are connected. That is, one should be able to move from the entrance to the exit tile by only moving up, down, left or right at each step, walking over floor tiles.
No floor tile is fully enclosed by wall tiles. That is, starting at any floor tile, one should be able to visit every other floor tile by moving only in those four directions, on floor tiles.
Let there be only one unique entrance-exit configuration, so one can assume that the entrance tile is at the bottom left corner and that the exit tile is at the upper right corner
How many valid mazes are there for a grid of size $n\times m$? ($n,m\ge2$)
That is, how can we find $N(n,m)$ - number of valid mazes as descrbed above?
Trivially, we have a simple bound;
Since the grid has $(nm-2)$ tiles that can either be a wall or floor, and at least $(n+m-3)$ of those tiles must be floor tiles, or we would not have a connected path from entrance to exit.
But I'm not sure how to count all of the invalid mazes that have unreachable floor tiles.
I've tried observing cases split into sets each with cases with $k$ walls to see how many invalid cases I can count depending on $k$ and $m,n$, but wasn't able to find a general pattern, nor was sure about it as I kept noticing I was missing cases or counting some more than once as I was not sure how to do it properly.