How do I approach problem JANE on spoj

general
, ,
1

problem : JANE

I think of : I have some state (J,T) and I want to reach (T,J) so I would start from (J,T) and look for each state (J+1,T-1) , (J-1,T-1) ,(J-1,T+1) and (J+1,T+1) and will do BFS and for all valid states of these ones.? but it is O(n^2)

1 Like
2

That would be \mathcal{O}(n^2) per starting index (J, T), which means it’s \mathcal{O}(n^4). I implemented an \mathcal{O}(n^2) approach which gives TLE, but I don’t see how it can be done better. If I think of something I’ll let you know.

1 Like
3

can u share ur approach?