Question link- http://www.spoj.com/problems/WATER/I am getting a WA for my solution but I couldn't find any test case for which my solution gives wrong answer. I am not using bfs or dfs but I am just maintaining 4 arrays left, right, up and down which store the value of the max height cuboid in the respective directions for every element. Finally for every element in the matrix I just add the min of the four arrays minus the element value to the result. Please help
This approach would take care of paths which are straight only. Zigzag paths wouldn't be taken into account. For example if your element is (2,2), your approach never takes into account paths like 2,2 -> 2,1 -> 1,1 ->1,0 .