TopCoder Statistics - Problem Statement

Problem Statement

You are given a rows x cols chessboard, and a cuboid with dimensions 1 x 1 x 3 standing on its small side (1 x 1) on one of the squares of the chessboard. You are trying to move the cuboid to another square, by tilting the cuboid over one of its base sides to some neighboring squares. The example figure below shows a 1 x 1 x 3 cuboid standing on the lower left square (first image). After the first move it lies on its 1 x 3 side in the middle of the lowest row (second image). After the second move it lies on its 1 x 3 side in the middle of the second lowest row. Finally, after the third move it is standing on its 1 x 1 side on the rightmost square of the second lowest row.

You are given rows and cols, specifying the number of rows and columns of the board. Further, you are given a int[] start and a int[] target, specifying the beginning and target positions of the cuboid, respectively. Both start and target will have exactly two elements. The first specifies the row and the second the column of the position (both 0-based). At the beginning, the cuboid is standing on its 1 x 1 side on the square specified by start. You are to return the minimum number of moves needed to move the cuboid so that it is standing on its 1 x 1 side on the square specified by target. During movement of the cuboid, no part of it may ever be outside the board limits specified by rows and cols. If the cuboid can not be moved to the target position, return -1. If the cuboid already is at the target square at the beginning, return 0.

Definition

Class:: RollingBlock
Method:: minMoves
Parameters:: int, int, int[], int[]
Returns:: int
Method signature:: int minMoves(int rows, int cols, int[] start, int[] target)
(be sure your method is public)

Constraints

rows and cols will be between 1 and 100, inclusive.
start and target will each have exactly 2 elements.
The first element of start and target will be between 0 and rows - 1, inclusive.
The second element of start and target will be between 0 and cols - 1, inclusive.

Examples

4

5

{3, 0}

{2, 4}

Returns: 3

The example from the problem statement (with rows numbered from back to front, columns numbered from left to right).
5

5

{2, 2}

{4, 0}

Returns: -1

The cuboid is at the center of a 5 x 5 board, tilting it to any side would bring part of the cuboid outside the board, so no move is possible.
4

4

{3, 0}

{3, 3}

Returns: 5

Tilt the cuboid up, then three times to the right, then down to arrive at the target position.
4

4

{3, 0}

{0, 3}

Returns: 10

First move the cuboid to {3, 3} in 5 moves (as in the previous example). With 5 further similar moves we can then move it to the target position.
100

100

{4, 5}

{5, 97}

Returns: 47
1

1

{0, 0}

{0, 0}

Returns: 0
1

2

{0, 0}

{0, 1}

Returns: -1
100

1

{1, 0}

{97, 0}

Returns: 48
100

1

{2, 0}

{96, 0}

Returns: -1
1

100

{0, 2}

{0, 97}

Returns: -1
4

100

{0, 2}

{0, 97}

Returns: 51
100

4

{3, 1}

{92, 2}

Returns: 50
100

4

{3, 1}

{91, 2}

Returns: 45
100

100

{50, 50}

{50, 50}

Returns: 0
100

100

{0, 99}

{99, 0}

Returns: 102
96

57

{56, 51}

{6, 40}

Returns: 33
48

99

{47, 13}

{3, 81}

Returns: 56
50

28

{31, 3}

{14, 5}

Returns: 13
91

9

{42, 1}

{5, 5}

Returns: 21
97

34

{74, 20}

{71, 6}

Returns: 11
97

51

{64, 4}

{41, 49}

Returns: 36
38

65

{11, 44}

{1, 41}

Returns: 9
40

46

{2, 26}

{10, 30}

Returns: 6
65

84

{3, 44}

{45, 10}

Returns: 40
52

14

{4, 9}

{30, 5}

Returns: 16
50

96

{8, 87}

{2, 35}

Returns: 30
70

78

{13, 0}

{55, 21}

Returns: 33
81

28

{1, 16}

{4, 12}

Returns: 5
47

90

{37, 59}

{6, 61}

Returns: 21
79

24

{13, 9}

{59, 23}

Returns: 32
11

54

{6, 37}

{4, 29}

Returns: 6
32

55

{11, 31}

{13, 1}

Returns: 20
81

41

{32, 26}

{19, 4}

Returns: 19
45

83

{20, 69}

{25, 51}

Returns: 13
19

11

{2, 10}

{2, 8}

Returns: 4
25

3

{6, 2}

{15, 1}

Returns: -1
3

88

{1, 83}

{1, 56}

Returns: -1
81

4

{52, 2}

{78, 0}

Returns: 18
66

48

{13, 13}

{3, 1}

Returns: 12
23

20

{18, 7}

{1, 7}

Returns: 11
13

13

{11, 3}

{10, 1}

Returns: 7
65

15

{3, 1}

{25, 5}

Returns: 14
50

65

{27, 20}

{34, 39}

Returns: 16
46

32

{36, 5}

{36, 15}

Returns: 8
29

54

{21, 52}

{12, 33}

Returns: 16
69

65

{42, 45}

{31, 34}

Returns: 14
64

31

{2, 7}

{56, 24}

Returns: 37
30

92

{0, 60}

{8, 40}

Returns: 14
21

71

{14, 40}

{17, 4}

Returns: 21
75

9

{39, 3}

{3, 2}

Returns: 19
67

54

{19, 53}

{54, 40}

Returns: 26
15

29

{5, 26}

{12, 7}

Returns: 16
8

33

{7, 25}

{1, 30}

Returns: 7
22

73

{9, 16}

{9, 54}

Returns: 22
82

44

{76, 13}

{49, 40}

Returns: 30
20

20

{7, 9}

{7, 9}

Returns: 0

The cuboid is already on the target square.
100

100

{4, 5 }

{5, 97 }

Returns: 47
4

4

{3, 0 }

{0, 3 }

Returns: 10
4

5

{3, 0 }

{2, 4 }

Returns: 3
100

100

{4, 5 }

{99, 97 }

Returns: 95
2

2

{0, 0 }

{1, 1 }

Returns: -1
80

30

{9, 5 }

{7, 9 }

Returns: 4
100

100

{0, 0 }

{99, 99 }

Returns: 102
8

8

{4, 4 }

{7, 7 }

Returns: 8
4

4

{0, 0 }

{1, 1 }

Returns: -1
11

12

{10, 10 }

{3, 2 }

Returns: 9
6

4

{1, 1 }

{2, 2 }

Returns: 10
5

4

{3, 0 }

{0, 3 }

Returns: 8
1

50

{0, 1 }

{0, 43 }

Returns: -1
56

70

{0, 67 }

{14, 2 }

Returns: 41
2

99

{0, 0 }

{1, 1 }

Returns: -1
6

6

{0, 0 }

{1, 1 }

Returns: 6
4

4

{0, 1 }

{3, 2 }

Returns: 12
100

100

{98, 99 }

{99, 98 }

Returns: 6
100

100

{3, 0 }

{4, 1 }

Returns: 6
7

6

{6, 1 }

{0, 4 }

Returns: 7

Statistics

Problem Statement for "RollingBlock"

Problem Statement

Definition

Constraints

Examples