## 10704 - Traffic!

Moderator: Board moderators

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

### 10704 - Traffic!

It seems a search problem . But how to save status?

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
I ve solved it yesterday. It's a simple "find the shortest path in graph", but it's tough to implement.
What you have to remember.
1. Every block has its column or row (depending on the type of the block). So to store a status you need to remember at most 18 numbers in the range [0..4] (there cant be more than 18 blocks). Plus, you need to remember the "weight" of the situation, its just one more integer.
2. The most interesting part for me was the structure that helps me find out weather a situation has already occured (therefore it shouldn't be considered). I used a tree-like structure for that. Lets say we have 3 blocks, and we've encountered only two situations : (0,2,4) and (0,2,2). the tree will look like this :

Code: Select all

``````    *
|
|0
*
|
|2
*
/ \
2/    \4
*       *
``````
If you come to the end of the tree the situation is not interesting, otherwise it is.
Hope this helps. I can also send my Pascal solution. Good Luck.
The more contests are held, the happier I am.

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Hi alex,
In the worst case, there're roughly 5^18=3814697265625 states. Did you assume that the tree will not grow up so rapidly, or you have proved an upper bound?
Thanks

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
No I never proved an upper bound. When I think of a 6x6 field I just don't believe that there is A WHOLE LOT of possible situations.
But since you asked me about it and its an interesting question, let's put it this way:
1. there are 12 lines in total, vertical and horizontal.
2. we can put 1 block in a line 5 different ways
we can put 2 blocks in a line 6 different ways
we can put 3 blocks in a line 1 different way
My rough upper bound 6^12 = 2176782336. But we must realize that two blocks in one line don't give much space for others to move around. Just think 12*2*2=48 cells occupied by our imaginary blocks. And the field is only 6*6=36!!!
And if we have one block in a line we get 5^12 = 24 million. Which is almost REAL.
P.S. You can write a recursive program and COUNT THEM ALL!
The more contests are held, the happier I am.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
LittleJohn wrote:Hi alex,
In the worst case, there're roughly 5^18=3814697265625 states. Did you assume that the tree will not grow up so rapidly, or you have proved an upper bound?
Thanks
I use hashing to solve this problem. I think it is possible to assume the tree will not grow up so rapidly. The argument is like this:
If there are a few blocks in the board, there are many possible move at each step. However, if the number of blocks is small, it should require small number of step to solve the puzzle, that is, the height of tree should be small.
If there are many number of blocks, although number of step is large, there are few possible move at each step. The number of state visited should be small in both case.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
Well in my tree the height is always equal to the number of blocks (if we measure the height in edges).
The more contests are held, the happier I am.

Lijiganjun
New poster
Posts: 5
Joined: Tue Dec 16, 2003 4:10 pm
Location: China
Contact:

### 10704 - Traffic!

Please give me some testdata ,3x!
Hello ,everyone!

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
For me, only this case is worth mentioning
1
0 4
0
0
0
0

The more contests are held, the happier I am.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Could you tell me what's wrong with my output? Are there any special cases?
13
4 1
4 0 1 0 2 4 3 0 0
1 3 0
6 3 2 1 3 2 1 2 3 0 3 5 1
0
4 1
1 4 0
0
6 3 0 5 2 4 3 0 0 0 2 3 2
2 1 0 2 2
1 1
2 1 3 1 0
0
3 4 1 3 0 2 1
3 0 1 3 2 5 1
2 1
1 3 1
1 1 0
4 0 3 0 1 2 3 3 3
1 5 1
0 1
2 0 3 4 3
1 0 0
4 4 0 5 1 3 3 1 1
2 3 0 2 2
3 1
3 4 2 1 3 2 0
0
5 0 1 3 3 4 0 4 3 5 3
1 1 0
4 1
0
1 3 0
4 1 0 2 2 3 1 4 3
2 1 2 5 2
1 1
1 1 3
3 0 0 3 1 3 0
4 4 3 3 2 2 1 0 2
1 5 2
4 2
0
1 0 0
4 3 2 5 3 1 3 3 0
2 2 1 0 2
5 1
3 1 3 1 0 0 2
1 3 0
1 5 3
1 3 2
2 1
1 2 3
1 0 0
3 0 1 4 2 5 1
2 1 2 3 0
4 2
0
0
0
0
4 1
3 4 3 3 0 1 0
0
4 0 0 3 3 0 2 1 2
2 2 1 5 0
Output:
The minimal number of moves to solve puzzle 1 is 4.
The minimal number of moves to solve puzzle 2 is 4.
The minimal number of moves to solve puzzle 3 is 4.
The minimal number of moves to solve puzzle 4 is 2.
The minimal number of moves to solve puzzle 5 is 4.
The minimal number of moves to solve puzzle 6 is 5.
The minimal number of moves to solve puzzle 7 is 4.
The minimal number of moves to solve puzzle 8 is 3.
The minimal number of moves to solve puzzle 9 is 1.
The minimal number of moves to solve puzzle 10 is 3.
The minimal number of moves to solve puzzle 11 is 3.
The minimal number of moves to solve puzzle 12 is 1.
The minimal number of moves to solve puzzle 13 is 5.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
My program replies:

Code: Select all

``````The minimal number of moves to solve puzzle 1 is 4.
The minimal number of moves to solve puzzle 5 is 7.
The minimal number of moves to solve puzzle 8 is 3.
The minimal number of moves to solve puzzle 9 is 1.
The minimal number of moves to solve puzzle 11 is 3.
The minimal number of moves to solve puzzle 12 is 1.
The minimal number of moves to solve puzzle 13 is 7.
``````
Where "NOT FOUND" is the unofficial reply it gives when it finishes the BFS without finding the exit.
In studying your second case, you either exit the field on the left side, or let another car exit first. Both are illegal.
Haven't looked at your other cases.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Thank you for reply. How do you know that left exit is illegal? There is nothing about it in the problem statement
Anyway, I changed my code to fit it to your output, but still no luck. Are there any special cases? What about those?
19
2 1
2 4 3 0 0
0
6 0 1 3 3 5 0 3 1 4 0 2 3
1 1 2
2 1
3 0 2 0 0 2 3
0
2 3 0 4 2
0
2 1
1 2 3
1 3 1
2 5 2 4 2
0
4 1
2 4 0 4 3
2 1 0 0 1
2 1 2 3 3
1 0 2
2 1
2 3 0 2 3
1 3 1
0
1 1 0
2 1
1 0 3
0
3 0 1 2 3 3 0
3 3 2 5 2 4 1
1 1
4 3 3 1 0 4 2 1 3
1 3 1
0
0
0 1
1 3 3
1 1 0
6 0 3 5 1 1 3 3 1 2 3 4 1
0
4 1
2 0 2 3 0
2 0 1 0 0
1 4 3
0
3 1
3 2 3 4 1 4 2
1 3 0
2 1 0 2 1
1 0 1
5 1
5 0 3 3 3 4 0 0 1 0 2
1 0 0
3 2 3 4 1 5 3
1 3 0
2 1
3 3 1 2 3 3 0
1 0 0
5 1 2 0 3 5 1 0 1 5 3
1 4 2
3 1
1 1 2
2 2 0 0 1
5 3 3 0 2 2 3 1 3 5 1
1 4 2
4 1
0
1 2 0
1 4 3
1 0 2
4 1
0
0
3 4 3 3 2 1 1
1 2 1
4 1
2 1 1 0 0
1 2 0
5 1 3 5 1 4 3 3 2 2 2
1 0 1
2 1
1 2 3
1 3 1
2 0 0 1 0
1 1 2
0 1
3 2 0 1 3 3 2
1 3 1
5 2 1 4 3 1 1 5 3 0 3
0
0 1
1 1 1
1 1 0
1 0 3
5 3 1 1 2 5 1 2 2 4 2
Output:
The minimal number of moves to solve puzzle 2 is 2.
The minimal number of moves to solve puzzle 3 is 2.
The minimal number of moves to solve puzzle 4 is 3.
The minimal number of moves to solve puzzle 5 is 2.
The minimal number of moves to solve puzzle 7 is 3.
The minimal number of moves to solve puzzle 10 is 2.
The minimal number of moves to solve puzzle 12 is 4.
The minimal number of moves to solve puzzle 17 is 2.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Krzysztof Duleba wrote:How do you know that left exit is illegal? There is nothing about it in the problem statement
You are right about that, although the arrow in the picture is pointing right.
Your output is the same as mine.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
I've just found my mistake. In BFS, I only moved vertical and horizontal blocks, but never the white one. Now I got AC - thanks for help.

Mr.south
New poster
Posts: 11
Joined: Thu Jan 25, 2007 1:45 pm
I got some problem from 10704

(1). is the exit always at right side?
(2). when you use BFS, do you use the branch :
1 position to the right, 2 positions to the right, or 3 positions to the right
or
you directly move the block to the bottom?
(3). Is there exist any solution that I need to move a block more than twice?

(4). you told that in your WA case you never move the white block, is the white block only moved at the last step?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Mr.south wrote:I got some problem from 10704

(1). is the exit always at right side?
(2). when you use BFS, do you use the branch :
1 position to the right, 2 positions to the right, or 3 positions to the right
or
you directly move the block to the bottom?
(3). Is there exist any solution that I need to move a block more than twice?

(4). you told that in your WA case you never move the white block, is the white block only moved at the last step?