Блог пользователя ahmadexe

Автор ahmadexe, история, 5 месяцев назад, По-английски

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

https://mirror.codeforces.com/contest/1948/submission/267884593

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ahmadexe (previous revision, new revision, compare).

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.codeforces.com/contest/1948/submission/267898619