##### Canadian Computing Competition: 2010 Stage 1, Junior #5

Below is an chessboard on which we will designate square locations using the ordered pairs as indicated. For example, notice that piece is at position and piece is at position .

8 | ||||||||
---|---|---|---|---|---|---|---|---|

7 | ||||||||

6 | ||||||||

5 | ||||||||

4 | ||||||||

3 | ||||||||

2 | ||||||||

1 | ||||||||

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

A knight is a special game piece that can leap over other pieces, moving in the "L" pattern. Specifically, in the diagram below, represents the knight's starting position and the numbers 1 through 8 represent possible places the knight may move to.

8 | ||||||||
---|---|---|---|---|---|---|---|---|

7 | ||||||||

6 | 8 | 1 | ||||||

5 | 7 | 2 | ||||||

4 | ||||||||

3 | 6 | 3 | ||||||

2 | 5 | 4 | ||||||

1 | ||||||||

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Your program will read the starting location of the knight and output the smallest number of jumps or moves needed to arrive at a location specified in the second input.

#### Input Specification

Your program will read four integers, where each integer is in the range . The first two integers represent the starting position of the knight. The second two integers represent the final position of the knight.

#### Output Specification

Your program should output the minimum (non-negative integer) number of moves required to move the knight from the starting position to the final position. Note that the knight is not allowed to move off the board during the sequence of moves.

#### Sample Input 1

```
2 1
3 3
```

#### Output for Sample Input 1

`1`

#### Sample Input 2

```
4 2
7 5
```

#### Output for Sample Input 2

`2`

## Comments

A chess knight will take at most 5 moves to reach a given square. I don't know if that bit of chess knowledge can be helpful for this problem.

It's actually 6 in some cases, such as from corner to corner.

Ah right, it is 6 moves. Sorry.

It helps you to become a grandmaster, but in reality, it has absolutely nothing to do with this question.

I was thinking you could pass the problem by setting an exit condition on recursion to be 5, instead of using a visited cache which is what I assume the problem intended.

Using

`std::queue`

with`pair<int,int>`

: https://dmoj.ca/submission/2145895 still MLE's.Edit: For comment below.

One mb ://

I mle by one mb on case 6 :(. Any optimization tips?

instead of making separate queues per dimension try using pairs to reduce the number of possible queue entries.

A queue of pair<int,int> still mle's. Maybe my BFS algorithm is inefficient? Best solutions only use like 1-2 mb.

Your program enters an infinite loop for the test case:

Thanks! I got it now!

Then it is most likely that you have a logical error/edge case you did not account for. The runtime for that case took abnormally long as well. I would advise you to look over the semantics.

You were right, I had

`if (visited.at(new_h).at(new_v) == 0)`

instead of`if (visited.at(new_v).at(new_h) == 0)`

.*facepalm

Edit: edits were glitching idk why

Did the point total for this question decrease?? I recall this being worth 10 points.

Yes, the points rewarded for this problems was reduced from 10 points to 7 points to match the other classical graph theory problems.

I think

What does IR mean and why do i get it when i submit

It means you got an

`Invalid Return`

.Refer to https://dmoj.ca/about/codes/

Which would be better?Using a Queue or recursive?

wleung_bvg you're getting it too?

Your code has variables that have indeterminate ("random") values. This can sometimes happen when declaring a variable in a non global scope without initializing it with a value. Simply initializing the boolean variable with the value

`false`

in your spot struct will allow your code to pass.Ah,thanks. Why does the first case work though?

No

`TLE`

when I submit in Java. Why does my C++ code get stuck when I submit, but never when I try cases on myself?TLECan anyone tell me why I'm getting

`TLE`

? I've tested my code with all the test data, and I get all the right answers. Given the fact that it's an 8 by 8 board, I find it very hard to believe my code is actually too slow. I even used a timer, with all cases under`0.1`

. Is my code getting stuck with the input or something?TLE means Time Limit Exceeded. time limit has nothing to do with answers, only the format you've coded the solution.

I know... My code wasn't too slow, as mentioned above. The struct bool wasn't initialized.

The judges can be wonky at times making your code run abnormally slow.

This was not the judges fault, as explained by wleung_bvg's reply. The judges may have been wonky in the past, but have lately been upgraded to provide very stable and also very fast run times.