fill point maximum

[Agamemnus]

Many of you know how "filling" an area with a certain color works. As some of you may also know, this is how the simplest pathfinding (search) works, too.

Now, the algorithm in question starts from one single point and moves out until there is nothing left to fill. From that point, 4 (or 8) points around it are checked, and then the points around them are checked, and so on. Call the points-to-be-checked the "fill points": any algorithm stores those fill points for the next iteration.

The challenge is to figure out a precise equation for a fill point maximum, given that the 2D array is of size xmax and ymax.

Assume that the fill progresses in 4 directions: N, S, E, W. (or 8 directions, or both combinations, if you're up to it)

The "block points" would be any points that stop the progression of fill points. On the map, "block points" can be in any combination. The fill point maximum comes from one particular arrangement of block points so that there is a maximum of fill points active at one time.

Here are two possible scenarios: (extremes)
1) No block points. Fill point maximum for that arrangement is:
(x ^ 2 + y ^ 2) * 4
(the fill pattern progresses in a diamond shape)

2) Maze configuration.
Assume that the maze looks like this:

Code:

|=====|
|     |
| |=| |
|   | |
|===| |
      |
======|

Thus, this gives a fill point maximum of 2.