breadth first search - SPOJ WATER : Developing a BFS algorithm -

i attempting solve following question spoj :

on rectangular mesh comprising nm fields, nm cuboids put, 1 cuboid on each field. base of each cuboid covers 1 field , surface equals 1 square inch. cuboids on adjacent fields adhere 1 close there no gaps between them. heavy rain pelted on construction in areas puddles of water appeared.

task

write program which:

• reads standard input size of chessboard , heights of cuboids put on fields
• computes maximal water volume, may gather in puddles after rain
• writes results in standard output.

input

the number of test cases t in first line of input, t test cases follow separated empty line. in first line of each test case 2 positive integers 1 <= n <= 100, 1 <= m <= 100 written. size of mesh. in each of following n lines there m integers interval [1..10000]; i-th number in j-th line denotes height of cuboid given in inches put on field in i-th column , j-th raw of chessboard.

output

your program should write each tes case 1 integer equal maximal volume of water (given in cubic inches), may gather in puddles on construction.

example  sample input: 1 3 6 3 3 4 4 4 2 3 1 3 2 1 4 7 3 1 6 4 1  sample output: 5 

i using bfs add how water flow border elements puddle(if theres path found). unable handle cases puddle maybe 2 consecutive cuboids. can me case?

here answer problem. speaking convenience, assume index start (1,1) (m,n)

as can imagine flow of water, water can travel higher cuboid lower cuboid ( there no revert direction i.e. water lower cuboid hit wall of higher cuboid , stop there).

so build graph g = (v,e) such v m x n vertices i.e. cuboid on matrix. edge connected (1-way only) connected cuboid i(th) cuboid j(th) when height(i) >= height(j) , (i , j physically connected)

so problem simple bfs.

by way, found 1 solve problem well. please take look

http://www.spojsolutions.com/212-water-among-cubes/