@swapnil159
Please Help
Try this test case:
1
3 3
zza
z#b
aae
1 Like
Thanks. It worked, i am getting wrong answer. can you please pinpoint whats the error in my code
I donāt think there is a problem with time limits because my queue solution worked. Infact I have quite few additional loops so I donāt think the time limit is very tight.
https://www.codechef.com/viewsolution/35692158
Make sure you have the valid and visited matrix. Throughout the contest my answer verdicts shuffled between TLE and WA all because I couldnāt think of a way to avoid dead end invalid paths. The use of valid matrix was a nice trick.
Can somebody please give a test case for which my code fails, itās already been over 3 hrs since I am bashing my head on finding the bug in my code
WA_SOLUTION
@avijit_agarwal @galencolin
I think it passes this test case. Are you sure?
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.