OJ Board

The main problem of floyd-warshall is the complexity of the algorithm O(n^3) while using a bfs or dfs per node the complexity is O(n^2).
I hope that will help you.

Khongor_SMCS wrote:Your tests are incorrect, in each coordinate x+y+z must equal to n

Thanks Khongor_SMCS. I checked the input data and the tests are currently correct.

It means that you have to put always a circle on a corner and the second one have to be connected with the first one.
Both circles have an angle with abscissa axis that goes from 0º to 90º and not always 45º as you consider.

SPOILER





You can delete r1+r2 of the width and r1+r2 of the height ...

I reckon that the statement is a little confusing. Could anyone say me what is the correct output for these cases?


3 4
2 0 1
3 0 0
0 2 1
0 3 0
3 2
0 0 3
0 1 2
2 3
2 0 0
1 1 0
0 2 0
3 4
1 0 2
1 1 1
2 0 1
3 0 0
3 4
3 0 0
2 0 1
1 0 2
0 1 2
2 3
0 1 1
1 1 0
2 0 0
3 4
3 0 0
2 1 0
1 2 0
0 3 0
2 2
1 0 1 ...

The diagonal is correct, but I think that it is better to find a way where you compare only integers.
Furthermore, You have to consider the possibility of include both circles in vertical or in horizontal.