Traktour's blog

lexicographically smallest path in a grid
By Traktour, history, 4 years ago, In English

Hello, I have some difficulties with this problem. Given a grid, you are initially in (1,1) and you want to go to (n,m) but you can't step in a cell with '#' you want to check if it is possible and show the lexicographically smallest path ( DDDRL)example of a path I thought of using bfs but it didn't work Thanks

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Could you explain the problem a bit clearly or post the link to the question?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider a grid n rows and m columns each cell can be either a "." Or "#" initially i am in cell (1,1) and i want to go to cell (n,m) i can't visit a cell that contain "#" I want to check if it is possible to go to (n,m) and if yes i want to print the lexicographically smallest path (The sequence of D R L U that i have done) D mean down L mean left R right and U up If for example DDL DLD are two possible paths i have to print DDL cause it is lexicoraphically the smallest Thank you

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Greedy DFS doesn't work?

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      I am still not satisfied with the explanation, like what are the constraints? Consider :
      S...
      #.#.
      ###F
      S being start and F being finish. Now which do you want me to output? RRRDD or RDURRDD or RDUDURRDD? Please state if you want the shortest path too.

      → Reply
»
4 years ago, # |
← Rev. 10   Vote: I like it +5 Vote: I do not like it

By DFS find out if each cell lies on any path from (1, 1) to (n, m). (Create a boolean n*m array, initialize all to false, if a cell lies on a valid path (any), make it true). You can do this by making all elements in the DFS recursion stack true whenever you get to (n, m).

Then greedy. Another DFS. Start from (1, 1). Look at all unvisited neighbors of your current cell which are set as true in the boolean array, then greedily choose the next cell.

Correct me if I'm wrong. (EDIT: This would be the lexicographically smallest path where no cell is repeated twice, and my solution does not minimise length) (Comment of kaons)

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Just do a BFS where at each cell, you look at adjacent cells in the order D L R U because that is the lexicographic order of the letters, so lexicographically smaller paths of the shortest length will take higher precedence than other shortest paths in the queue.

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Greedy should work i think?

You should provide the constraints and link of the problem if possible, but i believe since the lexicographically order of direction is "dlru" so we should try to go down as mush as we can then left and so on.

So i believe careful greedy should work? "Supposing that we can't visit the same cell twice".

→ Reply