How to solve this (1315) faster than 0.1 sec?

Which algo for this?

My algo like this:
For each cell i store: type (air, water or rock) and swim-air-capacity (number of cells can swim from this point)

After load I have map with air and rocks
First I filling topmost air-spaces with water and continue graph-fill to left to right and downwards, to determine which air-cells filled with water

Second, I make air-capacity for start-cell is D+1, and thent I start BFS-fill of map like this:
while cell-air-capacity is more than 0, i fill neighbour-cells: if neighbour-cell is air, set air-capacity to (D + 1), if water, and that air-capacity less than in this cell - then set air-capacity to value of this cell, decreased by 1.

If one of cells in topmost row filled with Air-capacity 2 or more, then result "Can be rescued by himself"

This algo takes 0,328 sec. But I can see in statistic there 0,031 and 0,045 sec results.

Which algo can do it faster?

Excuse my English )

Edited by author 06.06.2011 21:22