Page 1 of 1
10231 - Matrix World
Posted: Sun Apr 28, 2002 6:01 pm
by Adrian Kuegel
I think there is a map in the input without the current position. What is the output for this case?
And does a line contain only the caracters of the legend or something like spaces too.
And after collecting the last diamond treasure, must it be possible to go to the starting point back or not?
I really don't know why I get Wrong Answer.
Posted: Mon Apr 29, 2002 12:38 am
by Adrian Kuegel
I'm stupid. I declared my variable "time" in the same line as the map, which was of type char. Now I got Accepted.
I got WA!
Posted: Wed Mar 16, 2005 11:47 pm
by Moha
can anybody help me in this problem?
I have write this with DP, just like TSP but I got WA, please help me!.
Can anybody post some I/O in this problem?
thanks in advance
I got it!
Posted: Thu Mar 17, 2005 5:04 pm
by Moha
I got this problem. this sample revealed my bug:
- 30 30
..............XX..............
..............X...............
...............X..............
................X.............
.................X.........*..
..................X...........
...................X..........
....................X.........
.....................X........
......................X.......
.......................X......
........................X.....
.........................X....
..........................X...
...........................X..
.....*......................X.
*****O....*..................X
.....*......................X.
...........................X..
..........................X...
.........................X....
........................XX....
.......................X......
......................X.......
.....................X........
....................X.....*...
...................X..........
..................X...........
.................X............
..............................
My output is:
- Maximum number of collectible treasures: 8.
Minimum Time: 27 sec.
10231 Matrix World, WA
Posted: Sat Sep 17, 2005 9:52 am
by chuzpa
I think it is a tsp problem, am I wrong ?
I just measured the distance between the initial point, and the treasures's points, and the from each point to each other point ...
then I just did a backtracking to know how many treasures can I reach before any machine could reach it.
If a machine can reach a point before or in equal time than me, I don't pick up that treasure.
Is the idea ok ?
By the way if someone could post any input/output It would be great.
Posted: Sun Jun 18, 2006 11:08 pm
by Khaled_912
Sorry for the late reply, I've just got this problem accepted.
Your main idea seems OK, but there are some flaws.
Maybe I midunderstood what you said, but what do you mean by 'Measure the distance'?
It is indeed not the Euclidean distance; you must do BFS and find the shortest path from your position to every treasure, from every treasure to another treasure, and from every enemy to the treasure (I assumed the presence of more than one one enemy, the problem was not clear concerning this point).
Now I have a graph that is NOT fully connected (some obstacles might totally block objects to reach each other).
After constructing the graph, there comes the TSP, but with 10 nodes + all the BFS's you do, backtracking isn't the solution. I don't know how your backtacking solution didn't get a time limit, but you have to use the DP version of the TSP (in O(n^2*2^n) - still better than O(n!)).
I had a weird DP function, I built it top-down, and it returns a struct containing both the number of treasures and time. There might be a simpler solution, but is still works.
Here are some test cases and outputs from my AC code:
Input:
Code: Select all
5 5
X...#
####*
*****
****.
....O
3 3
***
###
O..
5 5
X...X
..*..
..*..
..O..
X...X
6 1
*
*
*
O
.
X
6 1
*
*
*
X
.
O
30 30
........................................
........................................
........................................
........................................
........................................
........................................
........................................
........................................
....*...................................
................*.......................
............................*...........
........................................
........................................
...*..............O.....................
........................................
........................................
........................................
........................................
............*..............*............
........................................
........................................
........................................
........................................
........................................
....*...................................
........................................
........................................
...................X....................
........................................
.........*..............................
............................*...........
........................................
........................................
........................................
.............*..........................
Output:
Code: Select all
Case 1:
Maximum number of collectible treasures: 10.
Minimum Time: 21 sec.
Case 2:
No treasures can be collected.
Case 3:
Maximum number of collectible treasures: 1.
Minimum Time: 2 sec.
Case 4:
Maximum number of collectible treasures: 1.
Minimum Time: 2 sec.
Case 5:
No treasures can be collected.
Case 6:
Maximum number of collectible treasures: 6.
Minimum Time: 65 sec.
Posted: Wed Jun 21, 2006 12:12 am
by chuzpa
hi there!
I've passed your I/Os but I think the last input is invalid because it has more characters than the actually especified. Does this especial case in the judge exist ?
Now I'm doing the problem like a DP TSP...
I don't know what is wrong hehehe, do you know more special cases ?
thanks...
Posted: Wed Jun 21, 2006 9:39 am
by chuzpa
hi there again, I've been testing my program ... but still no clue of what is wrong,
These are some of the inputs/ outputs I've got ...
INPUTS
Code: Select all
5 5
O....
....*
*...*
*..**
*.***
5 5
O....
*.*..
*....
*..**
*.**X
1 5
O***X
1 1
O
1 1
*
1 1
#
1 1
X
2 1
X
O
2 1
X
*
2 1
X
X
2 1
*
*
3 1
X
O
*
4 1
X
O
*
*
4 4
X#*.
.#..
..O.
*..*
4 4
X#**
.#..
..O.
*..*
10 10
O.........
..........
..........
..........
..........
..........
..........
..........
..........
..........
10 10
O......*..
..........
.*....*...
..........
..*.....*.
..........
*.....*...
..........
..*.......
.*......*.
4 10
O......*..
*.........
.*....*...
..........
4 10
O#.....*..
*######...
.*....*...
##........
4 10
O#X....*..
.######...
.*..*.....
*#........
4 10
O#........
.######...
.*..*.....
*#........
OUTPUTS
Code: Select all
Case 1:
Maximum number of collectible treasures: 10.
Minimum Time: 23 sec.
Case 2:
Maximum number of collectible treasures: 2.
Minimum Time: 4 sec.
Case 3:
Maximum number of collectible treasures: 1.
Minimum Time: 2 sec.
Case 4:
No treasures can be collected.
Case 5:
No treasures can be collected.
Case 6:
No treasures can be collected.
Case 7:
No treasures can be collected.
Case 8:
No treasures can be collected.
Case 9:
No treasures can be collected.
Case 10:
No treasures can be collected.
Case 11:
No treasures can be collected.
Case 12:
No treasures can be collected.
Case 13:
No treasures can be collected.
Case 14:
Maximum number of collectible treasures: 1.
Minimum Time: 3 sec.
Case 15:
Maximum number of collectible treasures: 2.
Minimum Time: 5 sec.
Case 16:
No treasures can be collected.
Case 17:
Maximum number of collectible treasures: 10.
Minimum Time: 49 sec.
Case 18:
Maximum number of collectible treasures: 4.
Minimum Time: 15 sec.
Case 19:
Maximum number of collectible treasures: 4.
Minimum Time: 15 sec.
Case 20:
Maximum number of collectible treasures: 3.
Minimum Time: 14 sec.
Case 21:
Maximum number of collectible treasures: 3.
Minimum Time: 11 sec.
Posted: Fri Jun 23, 2006 10:55 am
by chuzpa
I've got accepted, thanks for your help
:D