[z-musicians]

I'm interested in TC #5. Many people got TLE :-/

Is it something like

#.#.#.# and so on?

Ye i got the same problem....

Yes. Lot of small rooms with small free area. Most of them is 1.

And complex is huge.

Try to not call function every time, I do it without calling functions and it passed. I used stack, but this doesn't really matter.

BFS is best, i think, lot less recursive calls

I do have BFS and I don't have recursion. This stack method crossed my mind but I was too lazy to code it :)

DFS can not solve empty big complex in this time limit, Memory limit can be also critical as DFS make lot of recursive calls in similar case.

You need to calculate which algorithm is better.

Anyway 90 point not really bad at all!

there isn't big difference if you use stack or queue. my brother used stack too and he got 90 points. The only thing I can think of is the great number of function calling, try it to do without it.

I have problem with test case 5.
I got TLE, but I used stack and bfs without
recursion.

@mbaulunovic
I guess you don't think on the code of the competition because there you used dfs. So if you have wrote a new code it would be nice if you submit it,..

I found my mistake.
I used bfs function and every time it
created new stack.
It was > 16 mb

Any ideas how to improve this?
http://www.z-trening.com/new/www/html/submit.php?submit=7100021499&subm_code=1
I get memory limit exceeded on Test 4.

try to not do it recursive.

heh, I was hoping not to do it again..xD

You have to use BFS

ah, I tried hashing x and y and using dfs, didn't work, I'll do bfs now ... :)

I used bfs and I had TLE

My hint is don't use functions and make everything iterative :D

solved it with bfs...useful advice...i have 1 function thoughXD

me too...
I just first clear queue when I run that function ... :P

Solved with stack.

yeah i forgot i could do that XD

I used clock() to stop the program after 0.4 sec and it passed :)

Lol, why clock for this one, it was easy to pass :D

I suggest You to avoid use clock(). I don't know how is in Croatia, but in Serbia, on our competition, it is illegal to access system clock. If You do that, You risk to be disqualified. Read the rules from http://www.yuoi.nis.edu.yu/pravilnik.html
(black disc bullets near bottom of page)

That's not correct....u can use timer as much as you want on any competition...check cppreference to see what clock() is

You can do this in testing phase but final code, You send to grading, must be free of clock accessing routine.
You must be able to calculate yourself, time Your code need for particular task.

No, using clock IS allowed, as it only gives you the time your program is working, doesn't have anything to do with tampering with system time!

I don't know C++ well, can you please explain how does clock calculate the time your program is working?

Just gives you an int which represents how much time has passed since your program started....

SOLUTION: ------->>>

Move the declaration for queue< pair< int, int > > (or whatever) to the global scope (out of a function)! Tell me if this doesn't solve the problem

( This is why making everyhing iterative solved the problem, but this is the deeper reasoning )

At competition I got TLE on test No. 5, and I sent exactly the same code, just I deleted the procedure and put the code from procedure in my for loop and it passed :S

@nikola...
the same case happened to me....

passing to function requieres some time, in worst case (when you make bfs) there are 1000*1000/2 (if you have #.#.#.) function calls...

yeah, true...btw i think that passing just a pointer would speed it up...