589 - Pushing Boxes

[pc5971]

Who can give me some ideas about problem 589

[sohel]

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]

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.

[fh]

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

[shamim]

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]

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

[emotional blind]

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]

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]

Hi, fellows!

What's your reasoning for "Pushing Boxes" - UVa #589 ?
Is Heap data-structure is the most natural for this problem?

Regards,
serur

[Jan]

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

[serur]

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.

[sclo]

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]

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]

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]

I agreed with extremegf.