850784 15:24:03
20 May 2005 Fu Dong 1115 Pascal Accepted
 0.001 141 KB

I think the most important thing to this problem is to sort ships' length.

First I sorted them from short to long, but I got TLE on test #8, then I sorted from long to short, to my surprise, I got AC with 0.001s!

My solution is not DFS ! I think it O(x*n*MaxL)
with MaxL = Max( length row[i] , i=1..n ) .
But I haven't define how much x does yet !
Maybe x <= 10 ! I don't think your program run faster than mine because the test are not so hard.

To N.M.Hieu ( DHSP ):
  What's your way?

Sorry , I'm mistaken .
Mine is backtracking .
At that time , I was too young , so ...
I used DP to reduce the time of searching in bad result .
It's hard to say clearly due to my bad english .
If you want , leave me your email-address , I will mail you my solution , it's not good to pass the tests of problem 1394 ( Ship versions 2 ) but enough to pass those of this problem .