10796 - Right Hand Rule

[Zuza]

I got many WA becouse of this problem. Can somebodey werify the correctness of this test cases?

Code: Select all

19
20 20
1 17 19 0 0 19 D
###################.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.
....................
4 4
0 0 0 0 2 1 L
....
####
#..#
####
4 4
0 0 0 3 2 1 L
....
####
#..#
####
7 7
0 0 6 6 2 2 D
.......
.#####.
.#...#.
.#...#.
.#...#.
.#####.
.......
4 6
0 0 3 5 3 3 U
......
.####.
.#..#.
.##.#.
7 7
0 0 0 2 6 6 L
..#####
..#...#
......#
#.#####
..#....
.######
.......
3 4
0 1 2 2 2 2 U
...#
....
...#
7 7
0 0 6 6 6 6 L
..#####
..#...#
......#
#.#####
..#....
.######
.......
5 5
0 0 4 4 2 2 U
.....
.###.
.#.#.
.###.
..#..
2 10
1 2 1 5 1 3 L
##########
..........
20 20
1 1 19 7 16 3 L
####################
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#..................#
#.##################
#..................#
#######.##.........#
#.....#............#
#######.############
6 5
0 0 2 2 5 3 u
....#
.##.#
.#..#
.##.#
.##.#
.##.#
3 6
0 5 2 0 1 0 u
......
.####.
...#..
4 7
0 0 3 5 0 5 U
......#
.##.#.#
.##...#
.####.#
5 5
0 0 4 4 2 2 L
.....
.###.
.#.#.
.###.
.....
3 5
0 0 2 2 2 2 U
.....
##.##
...#.
10 10
1 1 9 2 9 2 U
##########
#........#
#.####.#.#
..#..#.#.#
.....#.#.#
.###.#.#.#
.#.#.#.#.#
.#.#.###.#
.#.#.....#
...#######
5 5
0 0 4 3 4 3 U
.....
##.#.
....#
.##.#
....#
5 5
0 0 2 3 3 3 U
.....
#####
.#..#
.#..#
.####

And my output is:

Code: Select all

Maze 1: 35
Maze 2: 0
Maze 3: 3
Maze 4: 12
Maze 5: 8
Maze 6: -1
Maze 7: 4
Maze 8: 23
Maze 9: 8
Maze 10: -1
Maze 11: 24
Maze 12: 9
Maze 13: -1
Maze 14: 8
Maze 15: 8
Maze 16: -1
Maze 17: 21
Maze 18: 15
Maze 19: -1

(Note that same of the cases are only tricky for the lenght of Agent Ks tour.)

[little joey]

They are correct, although the direction of Agent K should be a capital 'U' in cases 12 and 13.

[Zuza]

Thx Little Joey , I finally got Acc.

The Problem was that there was a (dirty ) trick in the input files (which I believe you already know about). I hope my input will help someone.

[Yarin]

Mwahaha, that was my small contribution to this problem. Thought it made things a bit more interesting

[Christian Schuster]

I just tried to solve this one with BFS, but got WA many times. I skipped the "states" where ME and K are in the same field or just exchanged positions. My program gives the correct answers for all inputs above, but here is another tricky case:

Code: Select all

1
2 3
0 0 0 2 0 1 R
...
###

Should the answer be -1 or 2? I assumed 2, because K "magically" apears at (0,1) and there is no collision. It could be -1 if K jumped between (0,1) and (0,2) while always facing right.

What about that "dirty trick"? Is there a difficult input case? Has it something to do with reading the input?

[Yarin]

You're right, the answer to that case should be 2 (that was the "dirty" input). That's really the only special case there is afaik.

[Christian Schuster]

Thank you. I missed a rare case in my automaton for the agent, making it run into an adjacent wall. Just fixed it and got AC.

[Spykaj]

My program passes all this tests and WA Any another ?

HELP HELP