When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ILoveShreya's blog

By ILoveShreya, history, 5 years ago, In English

I am trying to solve a bfs problem. But i am getting WA.First I try to find what's the wrong in my code without taking any help,then i have used SPOJ Toolkit with the available test case to find mistake in my code.But i'm again fail :(

Of course there is a problem in my code that's why i am getting WA but i haven't found it. My code link: code link.

Help please to find out why i'm getting WA.

Thank you advanced :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

i think it's not enough just keep the distances in vis[row][col], you need vis[row][col][dir].

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    After read your comment i also realize that...then i take vis[sz][sz][10] for store visited record with direction and also take an array dis[sz][sz] for store minimum move.But I'm still getting WA :) My update code.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      yes, i checked your code, and i think there is one problem with the input, so i changed this and now is giving TLE :(

      code

      Another point is, the way you model the graph makes him one weighted graph, because the lines 45~52 shows that there is two weights for one edge 0 or 1. So i changed your code to a djikstra, and got TLE, after i tried to use the 0-1BFS, and got TLE too :( .

      I guess the solution is, for each time when you are in a position (row, col), and the direction that you go is i, you use the move (dx[i], dy[i]) until you catch one blocked cell, you need to enqueue all cell's (x, y) that's is not visited, another observation is if you find one cell (x, y) that's already is visited, and her distance dis[x][y] < dis[ros][col] + 1, you can stop too. This way you just need the array dis[row][col] to store the distances, and not dis[row][col][dir].