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 ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
What kind of constrainsts?
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,
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 :(.
translated version to english by google.
Maybe 2 bfs's? IF (d1 % 2 == d2 % 2) answer is max(d1, d2) else INF?
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...
We can move by diagonals? If no, there isn't two paths with different parity.
PS Can we visit same cell twice?
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 =)
It actually can visit a cell twice.
T_T. Okay, I again misunderstood smth.
I think I've got some idea here, I'll try, then I'll post here,
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.
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.
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.
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] == '#')I'm coding this strategy now, soon I'll give you a feedback
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).