# Problem of the Week Problem C and Solution Crossing Canals

## Problem

Koji is rowing his boat on a busy canal system near his home. The following diagram shows the canal system with a star representing Koji’s current location and the house representing the location of his home.

From Koji’s extensive canal experience, he knows the following:

1. Rowing straight across an intersection square takes $$30$$ seconds.

2. Rowing straight across a square that is not an intersection takes $$20$$ seconds.

3. Turning right at an intersection takes $$15$$ seconds.

4. Turning left at an intersection takes $$270$$ seconds, due to heavy traffic.

5. It is not possible make U-turns or reverse direction.

Calculate the shortest amount of time it will take Koji to row home from his current position, using only the canals shown.

## Solution

Let $$R$$ represent a right turn, $$L$$ represent a left turn, $$X$$ represent a move straight across an intersection square, and $$N$$ represent a move straight across a non-intersection square.

We will now consider different routes and calculate the rowing time for each.

• The shortest route by distance is shown.

This corresponds to $$N \rightarrow L \rightarrow N \rightarrow N \rightarrow R \rightarrow N$$

Using the given times it would take

$$4\times 20+1\times 270+1\times 15=365$$ seconds.

• A second route is shown. This corresponds to

$$N\rightarrow X\rightarrow N\rightarrow N\rightarrow L\rightarrow N\rightarrow N\rightarrow L\rightarrow N$$

Using the given times it would take

$$6\times 20+2\times 270+1\times 30=690$$ seconds. This route is longer than the first and takes much more time.

• A third route is shown. This corresponds to

$$N\rightarrow X\rightarrow N\rightarrow N\rightarrow R\rightarrow N\rightarrow N\rightarrow R\rightarrow N\rightarrow N\rightarrow R\rightarrow N\rightarrow N\rightarrow X\rightarrow N\rightarrow N\rightarrow R\rightarrow N$$

Using the given times it would take

$$12\times 20+2\times 30+4\times 15=360$$ seconds. This route is longer than the previous two, but takes the least amount of time, so far.

• A fourth route is shown. This corresponds to

$$N\rightarrow R\rightarrow N\rightarrow N\rightarrow L\rightarrow N\rightarrow N\rightarrow L\rightarrow N\rightarrow N\rightarrow L\rightarrow N\rightarrow N\rightarrow R\rightarrow N\rightarrow N\rightarrow R\rightarrow N$$

Using the given times it would take

$$12\times 20+3\times 15+3\times 270=1095$$ seconds. This route takes much longer than the previous routes, due to all the left turns.

• A fifth route is shown. This corresponds to

$$N\rightarrow R\rightarrow N\rightarrow N\rightarrow L\rightarrow N\rightarrow N\rightarrow L\rightarrow N\rightarrow N\rightarrow X\rightarrow N\rightarrow N\rightarrow L\rightarrow N$$

Using the given times it would take

$$10\times 20+1\times 15+3\times 270+1\times 30=1055$$ seconds. This route also takes more time than the third route.

There are other routes that could be checked out but they include at least one of the above routes, so would not be the fastest.

Therefore, the shortest amount of time it will take Koji to row home is $$360$$ seconds.