Spoj problem A_W_S_N

general
, , , , ,
1

trying to solve Happy Valentine Day (Valentine Maze Game)

getting TLE :frowning: :frowning:

first i am mapping all my T, W and C to a map<pair, int>

then i am doing bfs to find all the minimum distances between all C, T and W

as C < 10 , T == 1, W == 1,

so a matrix[12][12] is crested and then jst back tracking the matrix from T to W via all C

i have also used dp with bitmask instead of backtrackingā€¦ but still TLE

can anyone suggest me any way to optimize the solution

my backtrack solution link

2

Try this one, unfortunately setting limit to 15s is broken on IdeOneā€¦

3

sorry but C < 10 in the problem
so for this my code wont workā€¦ for the input u had give to meā€¦

4

ok, my bad

5

can u suggest me any other approach for this problem

actually i m finding the minimum distance for each pair of C, T, w

and then jst backtracking itā€¦but its giving TLE

6

first thing, you can try is to replace all cin/cout with scanf/printfā€¦ or simply turn off buffering ( ios_base::sync_with_stdio(false) ) ā€¦

7

i am using scanf for input and as testcase are only 30 so cout or printf doesnt matterā€¦

8

i dont know what is this os_base::sync_with_stdio(false)??

and if i am using this in my code it is giving the initialised value of the variable i am priting and not changing it

without this its working fine

9

try the input in ideone, for 4 inputs it gets TLE, hope the input is ok now :wink:

10

can u suggest me how can i optimise the solution or any other approach to solve this ā€¦

11

i am not getting one thing 2 testcase with same input is working in 0.01 and if a similar testcase is added 3rd time its giving TLEā€¦strange

12

Maybe some memory issue, are you clearing memory?

Why you iterate cell by cells if bfs()? It seems to me, you want to find the best sequence of T - C1 - C2 - ā€¦ - CN - W, while N is atmost 10, 10! is ok on modern PC, but you can use queue just for those 12 points similarlyā€¦

13

in the last input again u add c > 10 so it was TLE nw its notā€¦

14

can u plz elaborate ur last comment actually i m not getting itā€¦

if i use DP bitmask instead of backtrack will this reduce the timeā€¦

15

@betlista thank u very much for ur time finally accepted using bitmask
please remove the ideone link that u have mentioned in ur first commemt

thank u man