aajjbb's blog

Counting steps in unweighted graph
By aajjbb, 12 years ago, In English

Hi, I have a problem which gives two mazes, and asks if it possible to travel from some vertex (a, b) to vertex (c, d) in A maze and, go from vertex (i, j) to (k, l) in maze B with the same number of steps(the number of steps in the path).

There's a way to check if it's possible to travel in a per-determined number of steps in a graph ?

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What kind of constrainsts?

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

    it's a N*N maze with chars, being 'R' the start point, 'F' the final point's and 'B' holes and '#' walls which aren't passable, N it between 1 and 50, this is the link:Link it's unfortunately in Portuguese,

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

      okay, here algorithm, by which you can calculate number of paths between 2 nodes of given length. I.e. you can calculate number of paths between node a and b of length 5. I think, now you can try all possible lengths and check them by this algo. link to algorithm. I hope you will understand it, it's in russian :(.

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

Maybe 2 bfs's? IF (d1 % 2 == d2 % 2) answer is max(d1, d2) else INF?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think no, cause we can chose not only shortest paths.
    Graph 1: shortest path is 4, but also we have path 5.
    Graph 2: shortest path is 3.
    Here we must chose in G1 way of length 5...

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      We can move by diagonals? If no, there isn't two paths with different parity.

      PS Can we visit same cell twice?

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

        Oh. Really, there's only 4 possible moves, checked from full statement.
        And we can't visit a cell twice.
        Sorry for wrong undestanding problem =)

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

          It actually can visit a cell twice.

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

            T_T. Okay, I again misunderstood smth.

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

              I think I've got some idea here, I'll try, then I'll post here,

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

    How would this BFS works ? just to clarify more, the robots have to make the same move in the same time I.E(if the robot in the first graph moves up(i, j — 1), the robot from the second graph have to do the same movement, and none of them can get in cells with 'B' or '#'. and it's asked to find whether is possible to find a path in both graphs which reach the goal cell 'F' in the same time.

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

      You just need to find shortest path in first graph and shortest path in second graph. And if parity of these paths is similar, then answer is the longest of paths, otherwise answer is INF. It's ValenKof's idea. And back to your question — shortest path in unweighted graph is sought by BFS.

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

        Unfortunately this strategy doesn't work, if you open the link, you'll see that for the second example, the length of the shortest paths are 4 and 8, but the answer is actually 12. it's really annoying since the two robots need to make the same sequence of moves.

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

          In a nutshell, you need to use one BFS to searching shortest path in graph with vertices (x1, y1, x2, y2). When you move to next vertex you just need to see that you can do it: f[x1][y1] != 'B' && f[x2][y2] != 'B' && !(f[x1][y1] == '#' && f[x2][y2] == '#')

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

            I'm coding this strategy now, soon I'll give you a feedback

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

      Well, it looks like bfs on graph with 4 parameters (coordinates of both robots). You must find shortest path from (a,b,i,j) to (c,d,k,l).

      → Reply