589 - Pushing Boxes

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

589 - Pushing Boxes

Post by pc5971 » Tue Nov 05, 2002 7:58 am

Who can give me some ideas about problem 589

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

589 TLE

Post by sohel » 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.

:-?

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » 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.
__nOi.m....

User avatar
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)

Post by fh » 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:
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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » 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.

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

Post by fh » Tue Jul 19, 2005 5:34 pm

Thanks, i've emailed the problemset@uva.es
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » 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

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » 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

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

Post by serur » 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
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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Nov 19, 2006 5:43 pm

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

Post by serur » 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.
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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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.

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

Re: 589 - Pushing Boxes

Post by extremegf » 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:

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

Post by extremegf » 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

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

Re: 589 - Pushing Boxes

Post by metaphysis » Tue Jun 06, 2017 5:01 am

I agreed with extremegf.

Post Reply

Return to “Volume 5 (500-599)”