The problem statement
This task can be solved easily with BFS. (Here is some more information about BFS). Just add the current position to the queue and every time check for it's neighbors, if there are any which are the next letter on our current position then add that cell to the queue as well. We have a problem with marking here. We can'r mark a cell as visited and forget about it because there might be another path which is being made with teh help of that cell . If we leave everything unmarked and don't use marking at all we will sure get a time limit exceeded error even with optimized input / output. We can just keep the number of times we visited one cell. And every cell has a total of 8 neighbors then we need to keep the number of times we visit the same cell and make sure that it won't exceed 8. See the source code for a better understanding.
Getting TLE on using BFS... How to tackle this?
ReplyDeleteI can't say right now, I need to have a look at your code but anyway, there are some things I can suggest, first of all have you noticed that the input is until 0 0. I didn't even use fast I/O. Post your code and we can see
Deletehow can you prove that maximum no.of times a cell needs to be visited is 8?
ReplyDeleteWhy does simply marking the visited cells visited and avoiding them in future paths give wrong answer??
ReplyDeletePlease help!!
ReplyDeletei guess if you have more than one A in the mAtrix then.. you need to find all the path and choose the longest one.. so if you mark the cells visited...then you can't use them in future.. so need to mark them un-visited..
ReplyDelete