Yes, I have the valid and visited matrices done beforehand. I don’t really understand the error here.
@galencolin
Actually initially we planned just to let the \mathcal{O}(N*M)) solution to pass so kept that high constant value of 10^7 but later decided that if anyone comes up with an solution having \mathcal{O}(N*M*log(min(n,m)))), it should be good enough to get an AC. So we increased the time limit to 2 sec and tested all three of C++, Java, and Python solutions on it. The above python solution here is actually a \mathcal{O}(N*M*log(min(n,m)))) solution. The solution you posted here has been tested to get an AC. I hope it clears the doubt. 
1 Like
@querty1234
your solution fails for this test case
1
3 17
sprrsprprrrpspsqs
rsqpsrrssppqqpsps
qpsrrprqqrrsrpppp
The actual output should be: sprqprrprqqrrsrpppp
but your code outputs: sprqpprprqqpqqppppp
@avijit_agarwal My solution is getting TLE in O(n*m). Can you tell me why it is getting TLE? Here is submission
this problem is same as min path sum in matrix.
but i could not get it how can i print min path?
please anyone can help me regarding this?
@vineetja
You are storing same points multiple times in your vector v1. Just use a visited array not to store the points multiple time.
Here’s your accepted solution - link
Hi! I am getting WA and unable to determine what case I am missing! Can somebody help me out.
Here’s my submission WA submission
My approach is almost similar to that of the author.
It did not on my laptop.
1 Like
Can we solve this by using Dijkstra’s from 1,1 to (n,m)?
If we convert all the characters to their ascii value (which represents the cost of moving from (a,b) to (x,y)) and then apply dijkstra is it doable?
@avijit_agarwal
No, azaaa will have a lower cost than aazzz but aazzz is lexicographically smaller.
2 Likes
Can you share link on online ide? Or the test case it fails?
Very strange. Maybe there are some memory issues with my solution because it passes the specific test case alone on all online ides as well as codechef ide. Can you share link on any online ide where some testcase fails. Thank you.
I am not objecting, but I am slightly puzzled. The question specifies a time limit of 2 seconds, yet my submission CodeChef: Practical coding for everyone passed with a time of 3.31 seconds. How come? Are time limits scaled for different languages (I am using Python 3, using the PyPy3 compiler)?
@aberent
Here in CodeChef, we have different time multiplers for different compilers.
You can learn more about it here.
1 Like
@avijit_agarwal could you help me know why this o(n*m) solution is TLE. Thanks CodeChef: Practical coding for everyone 10
hi @swapnil159
https://www.codechef.com/viewsolution/35703437
can you explain why i am getting tle in this??
Can someone look at My solution
i simply used DP algo for finding a path from [1,1] to [n,m] with ‘#’ as blocks
I don’t know on which test case it failed.
@avijit_agarwal @aman_robotics