10314 - Three Pigs

[Miguel Angel]

Could you PM a hard test case, i think i can give you the correct answer

[lky]

i use dfs to search all possible combination of the graph....any way to reduce time without coding again?

[Adrian Kuegel]

Repeat it 3 times and every time update the map, what's wrong??

Try this test case:

Code: Select all

1
8
1 0 0 1 0 0 0 1
1 2 0 2 1 2 2 0
1 2 1 2 1 2 2 0
1 2 0 0 1 1 1 1
1 2 0 2 2 2 2 1
1 2 1 0 0 0 0 1
1 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1

I think your program would output 27.
But correct solution is 28.
First step:

Code: Select all

x 0 0 1 0 0 0 1
x 2 0 2 1 2 2 0
x 2 1 2 1 2 2 0
x 2 0 0 1 1 1 1
x 2 0 2 2 2 2 1
x 2 1 0 0 0 0 1
x 2 2 2 2 2 2 1
x x x x x x x x

you get 15 acorns
Second step:

Code: Select all

x x x x x x x x
0 2 0 2 1 2 2 x
0 2 1 2 1 2 2 x
0 2 x x x x x x
0 2 x 2 2 2 2 1
0 2 x x x x x x
0 2 2 2 2 2 2 x
0 0 0 0 0 0 0 x

you get 9 acorns (note, there is a way to reach 10 acorns, but you should not use it).
Third step:

Code: Select all

x x x 0 x x x x
0 2 x 2 x 2 2 x
0 2 x 2 x 2 2 x
0 2 x x x 0 0 x
0 2 0 2 2 2 2 x
0 2 0 0 0 0 0 x
0 2 2 2 2 2 2 x
0 0 0 0 0 0 0 x

you get 4 acorns
15 + 9 + 4 = 28

[HYri]

To Revenger

5
1 1 1 1 1
2 1 2 2 1
2 1 1 2 1
2 1 1 2 1
2 2 2 2 1

how could it be 9?

isn't it -1? there's no ways for "Three" pig..?

[polone]

Three pigs is not claimed that they should use different ways

[RC's]

I got TLE using DFS and backtracking.. I don't know how to optimize my code. How can I know if one path has been taken and so that another pigs will not follow the exactly same path ? some say using DP.. but I don't know how because I am bad at DP.. Can anyone give me hint ?