| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
i am trying to solve http://www.spoj.com/problems/BITMAP/ problem.
my code is giving TLE on SPOJ .
i am not getting why it's getting TLE.
i approached in this procedure: I stored those pixels which have value 1 in a queue and applied bfs across these,
my code is http://ideone.com/ppgQiW
please help
thanks
If I understood your code right you do multiple BFS's and all of them pass by all the vertices. That results in a high complexity since there may be up to n*m BFS's, each of them executed in O(n*m).
Try to solve it with only one "complex" BFS that may pass by each vertex more than once, in case a better value for it is found.
This is the code I used: Don't click me . If you still need help message me.
This problem is beautiful, I highly recommend everyone learning basic graph algorithms to solve it.
You can add all white pixels to the BFS queue at the beginning, then the BFS will find all required distances visiting each vertex only once.
I have done exacltly that i.e running bfs across those points which are white, but I am getting TLE. Please have a look at my code probably you will understand why I am getting TLE.
You start a new BFS from each white pixel. There's no point in adding a lot of vertices to the BFS at the beginning if then you're gonna create a new queue and a new visited array everytime you pop an element from the queue.
You have to add all white pixels to the queue and then use that very same queue to do the BFS only once.