## 589 - Pushing Boxes

Moderator: Board moderators

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

### 589 - Pushing Boxes

Who can give me some ideas about problem 589

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 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.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
sohel,
i Accepted this problem. But my program runs not so fast.

any way, i think you determine all path. You don't have to do that if you use shortest path algorithm. This can minimize your time enough.
__nOi.m....

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

### 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:
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.
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:

Code: Select all

``````4 5
.....
..BS.
.#.#.
T....``````
My program attempts to move the 'B' to South, yielding the output:

Code: Select all

``````Maze #1
nwSSneesswWW``````
Notice that box moves is in uppercase letter, it moves South first (according to my BFS priority). Whereas the correct output should be:

Code: Select all

``````Maze #1
WWnwSS``````
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:

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
``````
CORRECT OUTPUT:

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``````
This http://acm.uva.es/p site has been very helpful in providing service for me (and everyone) in practicing algorithms. Keep it up
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
Thanks, i've emailed the problemset@uva.es
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
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

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
``````
output

Code: Select all

``````Maze #1
wnNwwwnneeeSnwwwsseeEEE

Maze #2
wnNNNNNennwSSSSSesWWWswwnEEEEEE

Maze #3
wnNNNNNeennwwSSSSSesWWWswwnEEEEEE

Maze #4
Impossible.

Maze #5
Impossible.

Maze #6
NsseennnwWWWWWWWWWWWWWWWWW

``````
best wishes

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
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

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
``````
output

Code: Select all

``````Maze #1
wnNwwwnneeeSnwwwsseeEEE

Maze #2
wnNNNNNennwSSSSSesWWWswwnEEEEEE

Maze #3
wnNNNNNeennwwSSSSSesWWWswwnEEEEEE

Maze #4
Impossible.

Maze #5
Impossible.

Maze #6
NsseennnwWWWWWWWWWWWWWWWWW

``````
best wishes

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 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
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I have solved it with BFS. But you can also use heaps.
Ami ekhono shopno dekhi...
HomePage

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
There's at least 2 ways of solving this one:
Use a heap or priority queue
Use 2 queues for bfs. One for walking and one for pushing.

extremegf
New poster
Posts: 2
Joined: Sun Nov 22, 2015 2:44 pm

### 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:

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

``````
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.

extremegf
New poster
Posts: 2
Joined: Sun Nov 22, 2015 2:44 pm

### 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
``````

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 589 - Pushing Boxes

I agreed with extremegf.