| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 150 |
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