| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 165 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 151 |
| 5 | nor | 151 |
| 7 | atcoder_official | 147 |
| 8 | TheScrasse | 146 |
| 9 | Petr | 145 |
| 10 | SecondThread | 142 |
So I am a newbie in DFS and BFS, and was solving this problem. Surprisingly, giving TLE in 3rd testcase. I can't seem to understand where code is inefficient since time complexity is looking fine to me.
I have added some comments, which don't use the ideal terminologies but would hopefully convey what I'm trying to do
Auto comment: topic has been updated by ahmadexe (previous revision, new revision, compare).
I modified 3 things in your code and got Accepted. 1- I added a condition to check whether the variable s is out of the grid (aka s < 0 || s >= n) 2- Instead of 5 conditions to check whether the new position the robot is gonna move to is visited or not, I used one condition after the "q.pop()" line to handle the visited cases alongside with the "out of the grid" cases. 3- last but not lease, instead of marking the element visited[f][s][t] as visited, you only need to mark the element visited[f][s][0] as visited; not the visited[f][s][1]. That's because in case you reached a position with t = 1, it does not matter whether it is visited or not, cos the robot is going to follow the arrow nevertheless.
Here's the new submission: https://codeforces.net/contest/1948/submission/267898619
Thanks alot for your explanation. Works now