### 589 - Pushing Boxes

Posted:

**Tue Nov 05, 2002 7:58 am**Who can give me some ideas about problem 589

Page **1** of **1**

Posted: **Tue Nov 05, 2002 7:58 am**

Who can give me some ideas about problem 589

Posted: **Mon Apr 26, 2004 12:40 pm**

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.

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.

Posted: **Wed Oct 13, 2004 9:21 pm**

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.

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.

Posted: **Sun Jul 17, 2005 1:10 pm**

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

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

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

Posted: **Tue Jul 19, 2005 10:52 am**

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.

Posted: **Tue Jul 19, 2005 5:34 pm**

Thanks, i've emailed the problemset@uva.es

Posted: **Sat Dec 10, 2005 8:33 am**

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

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

Posted: **Sat Dec 10, 2005 8:34 am**

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

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

Posted: **Thu Nov 16, 2006 7:05 pm**

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

Posted: **Sun Nov 19, 2006 5:43 pm**

I have solved it with BFS. But you can also use heaps.

Posted: **Tue Jan 09, 2007 9:27 am**

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.

Posted: **Mon Aug 27, 2007 6:23 pm**

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.

Use a heap or priority queue

Use 2 queues for bfs. One for walking and one for pushing.

Posted: **Sun Nov 22, 2015 2:59 pm**

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

Posted: **Sun Nov 22, 2015 3:49 pm**

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

Posted: **Tue Jun 06, 2017 5:01 am**

I agreed with extremegf.