Finally I got AC.

The English statement is so confused that I feel it necessary to make something clear here.

1 What does SURFACE mean?
The surface means the uppermost row, in the other word, the row above the first input row. ONLY this row could be regarded as the surface. It means, the water could only pour in from these 'holes', and the man will rescue if he could reach the uppermost row.

2 What does the STARTING POINT mean?
The starting point could be ANYWHERE in the cave, even could be a BLOCKED cube (the cube with '#')(Test #22).
When we got the coordinate of the starting point, first notice that the Y-coordinate begins from the bottom. Then, you should do searching. Here:
(1) DO NOT think a blocked starting point means "rescue operation required". Just regard it as a empty cell and continue.
(2) When the man starts, he is at the starting point. Now he have just D-cube breaths, not D-1. That means the following testcase is correct:
3 3 2 1 3
#.#
#.#
#.#
Can be rescued by himself.
SO, IN ONE WORD, the starting point, although may be blocked or flooded with water, we can regard it as a place to breath as if it is empty without water.

3 How long could he stay in water?
Through D cubes. If you look at the samples carefully, you will get the answer, without the mistake of D and D-1.

4 What does "Here only the paths having no downward segments are considered" in statement mean?
It means the water could only flow lower and lower, not higher in any cases. So, in the sample data, the (5,3) cube will not be flooded with water and this cube can be used to breathe.

5 What does "It is known that a speleologist can reach the surface while cave is not filled with water." in statement mean?
It means there exist a path from the starting point to the surface. If there is no water, or the man has infinite breathe, he could reach the surface.

6 What is the time complexity of the problem?
O(W*H) could be achieved, though O(W*H*D) might have AC, too.

Hope the instructions above could help someone in trouble.

why for D==5 answer is "NO"?

I sended many times and I know test #3.

<!-- begin test 3 -->
10 10 2 2 10
#........#
#.....####
#...###.##
#........#
#....###.#
#....#.#.#
###.#....#
#.##.###.#
#........#
##########
<!--end test 3 -->

The answer for this input is "Can be rescued by himself"
But how it could be?
The minimum length of the path is 20.

Or speleologist can swim between two diagonal blocks?
But how? the problem description isn't clear about it.

Somebody who has got AC, please, clarify...

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

The limitations in the problem statement were decreased. New limitations are W, H ≤ 500; D ≤ 1000. Tests were fixed according to these limitations. New tests were added. All submits were rejudged. 5 submits got AC verdict, 41 submit lost AC verdict. Thanks to Sergey Vedernikov and Roman Rizvanov for new tests

In the text, what does the word SURFACE mean?

Consider the following case:
3 6 2 2 3
#.#
#.#
#.#
#.#
...
###

Can he rescued by himself??????

What's the trick on Test #11?..

Help me ...

1)What is considered to be surface?
the row with y == h + 1 or any cell out of cave?
What that?
1 2 1 1 1
.
.

2)May water flows not only from the higher row?
3 3 2 2 1
###
...
...
?

I dont know what leads to my wa11 ( any hints?

please give me some tests!

Some new tests were added. About 40 submits lost AC verdict. Maybe I will add more tests soon. If your AC solution works slow on some test you may post a structure of tricky test in this topic, and I will add it.

Help me, please with this test.

In test 11 D>1000!

What is the system of coordinates in this task ?
Write me as example:
1 2 3 4 ... w
2
.
.
h
and where is the (8,2)in this table:
##..##..#
##.#.####
##......#
######### ?

 and a space " " denotes air
in Russian description, there is a "." and in sample input there are "."

So what is " ", "." and the atom denotes air finally?

I'm so confused.

if human started in filled '#' position,
do not write instantly 'Rescue operation required'...
run search process in any case.

...the magic "i:=i div(i-i)" helped us.

The test data seems to be weak. My O(N*M*D) solution without any optimizations gets AC within 0.56 sec! Just faint...

Hi!

I have few questions about this tasks.

1-st) How do we enumerate Y coordinate?
If assuming following sample test case
##..##..#
##.#.####
##.....x# 2
#########
Where x is speleologist we can have 2 variants:

##..##..# 0  4
##.#.#### 1  3
##.....x# 2  2
######### 3  1

I think surface = 0 must be the correct one, because then I have
WA on 9-th case else I have WA on 4-th.

2-nd) How should we calculate amount of swimmed blocks?
In another words: what is length of straight route from (1; 2) to
(1, 4): it goes through 3 cells: (1; 2), (1; 3) and  (1; 4)
and if we consider centers then route has length of 2.

Lets consider sample test case where w means water
##ww##ww#
##w#!####
##wwwwww#
#########
First we can swim 4 left and 1 up -> we are at ! symbol. Now we
have to swim up to the surface:
##5w##ww#
##4#!####
##321www#
#########
So we are currently on surface in 5 moves so both answers should be
"Can be rescued by himself".

Could you please point place where I had mistaken...