589 - Pushing Boxes
Moderator: Board moderators
589 - Pushing Boxes
Who can give me some ideas about problem 589
589 TLE
I used BFS to solve( well tried to
) this problem and got TLE..
I maintained a four dimentional array d[][][][], where
d[1][3][5][4] determines the state where the box is at 1,3 and the man is at 5,4;........ and updated the array accordingly. Then I considered all the path that reaches the target and the answer is the one with the smallest number of Capital letters..
... what am I doing wrong? is there a better way of making it efficeint.
![:-?](./images/smilies/icon_confused.gif)
![:)](./images/smilies/icon_smile.gif)
I maintained a four dimentional array d[][][][], where
d[1][3][5][4] determines the state where the box is at 1,3 and the man is at 5,4;........ and updated the array accordingly. Then I considered all the path that reaches the target and the answer is the one with the smallest number of Capital letters..
... what am I doing wrong? is there a better way of making it efficeint.
![:-?](./images/smilies/icon_confused.gif)
589 - Pushing Boxes (judge is lacking some test case)
Problem #589 is an interesting problem (at least for me). I spent my whole day "tuning" my algorithms on this problem. After optimizing several times: deleting parts of the code and re-submit, I realize that the judge is lacking of input case to test for number of walks and pushes. This is what the problem statement says:
My program attempts to move the 'B' to South, yielding the output:
Notice that box moves is in uppercase letter, it moves South first (according to my BFS priority). Whereas the correct output should be:
Both of the output has the same number of "pushes" but not the same number of "walks". According to the problem statement, the latter output is the correct one. But my program got Accepted when I submit to the judge. This explains the lacking input from the judge to test the "walks".
I think it's best to rejudge the problem? or leave as it is? Anyway, if the Admin wants to rejudge, below is the test cases to attack those who didn't check the "walks". It works for any BFS priority:
- Those who has South as 1st BFS priority will fail on Maze #1 and Maze #2
- Those who has North as 1st BFS priority will fail on Maze #3 and Maze #4
- Those who has East as 1st BFS priority will fail on Maze #5 and Maze #6
- Those who has West as 1st BFS priority will fail on Maze #7 and Maze #8
INPUT:
CORRECT OUTPUT:
This http://acm.uva.es/p site has been very helpful in providing service for me (and everyone) in practicing algorithms. Keep it up ![:)](./images/smilies/icon_smile.gif)
I solve the problem using 2 "nested" BFS. The first is to move the 'B' (box) and the second BFS (the nested one) is to ensure that the 'S' (you) can find it's way to arrive behind the box (to push the box). However my BFS has "priority" (every BFS has). It seeks and generate a "node" for South first, then North, then West, and then East. So, my solution should fail on the following test case:Otherwise, output a sequence that minimizes the number of pushes. If there is more than one such sequence, choose the one that minimizes the number of total moves (walks and pushes). If there is still more than one such sequence, any one is acceptable.
Code: Select all
4 5
.....
..BS.
.#.#.
T....
Code: Select all
Maze #1
nwSSneesswWW
Code: Select all
Maze #1
WWnwSS
I think it's best to rejudge the problem? or leave as it is? Anyway, if the Admin wants to rejudge, below is the test cases to attack those who didn't check the "walks". It works for any BFS priority:
- Those who has South as 1st BFS priority will fail on Maze #1 and Maze #2
- Those who has North as 1st BFS priority will fail on Maze #3 and Maze #4
- Those who has East as 1st BFS priority will fail on Maze #5 and Maze #6
- Those who has West as 1st BFS priority will fail on Maze #7 and Maze #8
INPUT:
Code: Select all
4 5
.....
..BS.
.#.#.
T....
4 5
.....
.SB..
.#.#.
....T
4 5
T....
.#.#.
..BS.
.....
4 5
....T
.#.#.
.SB..
.....
5 4
...T
..#.
.B..
.S#.
....
5 4
....
.S#.
.B..
..#.
...T
5 4
....
.#S.
..B.
.#..
T...
5 4
T...
.#..
..B.
.#S.
....
0 0
Code: Select all
Maze #1
WWnwSS
Maze #2
EEneSS
Maze #3
WWswNN
Maze #4
EEseNN
Maze #5
NNwnEE
Maze #6
SSwsEE
Maze #7
SSesWW
Maze #8
NNenWW
![:)](./images/smilies/icon_smile.gif)
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
Nice that you have done some work to find cases that are not present but should be to catch bad solutions.
Actually, in such cases, it better to mail the information to the following address.
problemset@uva.es
The admins really don't read much of the posts in this thread but they will respond to the mails.
Actually, in such cases, it better to mail the information to the following address.
problemset@uva.es
The admins really don't read much of the posts in this thread but they will respond to the mails.
Thanks, i've emailed the problemset@uva.es
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
it can be solved using BFS
two modification of BFS
one for B and one for S
i can give you some sample input output
input
output
best wishes
two modification of BFS
one for B and one for S
i can give you some sample input output
input
Code: Select all
12 11
###########
#.#.......#
#.###..####
#...#...#.#
#####.##..#
#.....#...#
##.##...###
#....B..T##
#...#.#####
#####.S..##
##...######
###########
12 11
###########
#.#.......#
#.###..####
#...#...#.#
#####.##..#
#...#.#...#
##.##...###
#....B..T##
#...#.#####
#####.S..##
##...######
###########
12 11
##.....####
#.........#
#.###.#.###
#...#...#.#
#####.##..#
#...#.#...#
##.##...###
#....B..T##
#...#.#####
#####.S..##
##...######
###########
20 20
T..................B
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
...................S
20 20
T...................
................#B#.
................#S#.
.................#..
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
20 20
T...................
................#B#.
................#S#.
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
0 0
Code: Select all
Maze #1
wnNwwwnneeeSnwwwsseeEEE
Maze #2
wnNNNNNennwSSSSSesWWWswwnEEEEEE
Maze #3
wnNNNNNeennwwSSSSSesWWWswwnEEEEEE
Maze #4
Impossible.
Maze #5
Impossible.
Maze #6
NsseennnwWWWWWWWWWWWWWWWWW
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
it can be solved using BFS
two modification of BFS
one for B and one for S
i can give you some sample input output
input
output
best wishes
two modification of BFS
one for B and one for S
i can give you some sample input output
input
Code: Select all
12 11
###########
#.#.......#
#.###..####
#...#...#.#
#####.##..#
#.....#...#
##.##...###
#....B..T##
#...#.#####
#####.S..##
##...######
###########
12 11
###########
#.#.......#
#.###..####
#...#...#.#
#####.##..#
#...#.#...#
##.##...###
#....B..T##
#...#.#####
#####.S..##
##...######
###########
12 11
##.....####
#.........#
#.###.#.###
#...#...#.#
#####.##..#
#...#.#...#
##.##...###
#....B..T##
#...#.#####
#####.S..##
##...######
###########
20 20
T..................B
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
...................S
20 20
T...................
................#B#.
................#S#.
.................#..
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
20 20
T...................
................#B#.
................#S#.
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
0 0
Code: Select all
Maze #1
wnNwwwnneeeSnwwwsseeEEE
Maze #2
wnNNNNNennwSSSSSesWWWswwnEEEEEE
Maze #3
wnNNNNNeennwwSSSSSesWWWswwnEEEEEE
Maze #4
Impossible.
Maze #5
Impossible.
Maze #6
NsseennnwWWWWWWWWWWWWWWWWW
589
Hi, fellows!
What's your reasoning for "Pushing Boxes" - UVa #589 ?
Is Heap data-structure is the most natural for this problem?
Regards,
serur
What's your reasoning for "Pushing Boxes" - UVa #589 ?
Is Heap data-structure is the most natural for this problem?
Regards,
serur
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
Hi, Jan.
Thank you for reply. It appears "Pushing Boxes" is an easy one - cheetah got it AC with 0.008 CPU, but I myself got it with 1,5 CPU. It was the first time I used heaps and the so-called "Best-First Search".
This problem is from the ACM-contest held in University of Ulm, 1997(SWERC), and I'm grateful to Matthias Ruhl for his code. I hope someone - e.g. Adrian Kuegel - can tell us who is this nice guy.
Thank you for reply. It appears "Pushing Boxes" is an easy one - cheetah got it AC with 0.008 CPU, but I myself got it with 1,5 CPU. It was the first time I used heaps and the so-called "Best-First Search".
This problem is from the ACM-contest held in University of Ulm, 1997(SWERC), and I'm grateful to Matthias Ruhl for his code. I hope someone - e.g. Adrian Kuegel - can tell us who is this nice guy.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
Re: 589 - Pushing Boxes
The test set for this task is still invalid. I just got an AC with a two BFS solution, which isn't correct. I claim that no two BFS algorithm can solve this problem and it actually requires a full shortest paths algorithm like dijkstra.
Consider following 2 graphs:
Any double BFS solution will always choose path S, c, d, T or S, a, b, T, for both graphs. Double BFS can not distinguish between these two. And it will give a wrong answer.
Consider following 2 graphs:
Code: Select all
S - source node
T - destination node
Shortcut notation for a series of nodes:
-n-> - walk (no box pushing) path of length n
=n=> - box push path of length n
Graph I:
S -1-> a =1=> b -1000-> T
S -100-> c =1=> d -1-> T
Graph II:
S -1-> a =1=> b -100-> T
S -1000-> c =1=> d -1-> T
Re: 589 - Pushing Boxes
Ok, I've decided to go one step forward with this. These cases demonstrate my point:
Code: Select all
15 18
##################
##################
##################
##################
##################
##################
T#################
.##########...####
.......####.#.####
..##.#.####.#.####
.###...####.#.####
.###.######.#.####
....B.......#.####
..##.########.####
####S.........####
15 18
........##########
.######.##########
......#.##########
#####.#...........
#####.###########.
#####.###.........
T####..##.########
.#####.##.#...####
.......##.#.#.####
..##.####.#.#.####
.###......#.#.####
.###.######.#.####
....B.......#.####
..##.########.####
####S.........####
0 0
-
- Experienced poster
- Posts: 139
- Joined: Wed May 18, 2011 3:04 pm
Re: 589 - Pushing Boxes
I agreed with extremegf.
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.