## Birthday Cake solution kickstart

Table of Contents

## Problem

You are given a grid of RR rows and CC columns that corresponds to a birthday cake.

The rows are numbered from 11 to RR starting from the top. The columns are numbered from 11 to CC starting from the left. Each cell in the grid is a square of size 1×11×1.

You noticed that the most delicious part of the cake forms a single filled rectangle; that means all the cells inside this single rectangle will be delicious as well, but all the cells outside this rectangle are not delicious.

You have a knife that is long enough to make straight-line cuts of length up to KK. Birthday Cake solution kickstartWe want to make a series of cuts to extract each of the delicious cells separately, so that we can put candles on them, and enjoy the birthday party. Birthday Cake solution kickstart

To extract each of the delicious cells separately, they must be disconnected from any other cell.

A cell is disconnected if no other cell is connected to it in any of the 44 directions (up, down, left, right).A cut is a directed line segment which is valid if the following conditions are met:

- The cut runs along one of the horizontal or vertical lines between the rows and columns of the grid.
- The length of the cut must not exceed KK.
- The starting and ending points of the cut must be grid points (i.e. a corner of a cell). In addition, the starting point must be already exposed, meaning that it lies on one of the 44 sides of the grid or on one of the previous cuts.
- The cut must not pass through any other exposed points. It may touch an exposed point, but if it does, it must end right there.

Suppose that K=4K=4. Below you can find five examples of valid cuts.

And here are four examples of invalid cuts

- In the first picture, the cut is too long (longer than 44).
- In the second picture, the cut starts from an unexposed point (neither one of the 44 sides of the grid nor a previous cut).
- In the third picture, the cut passes through an exposed point, it must stop once it touches the exposed point at length 22.
- The fourth picture is invalid because of the same reason as the third picture.
We need to find the minimum number of cuts needed to extract all the delicious cells.

## Input

The first line of the input gives the number of test cases, TT. TT test cases follow.

Each test case starts with a line containing three integers, RR, CC and KK.

The next line contains four integers, r1r1, c1c1, r2r2, c2c2, representing the top-left and bottom-right cell of the delicious rectangle respectively.## Output

For each test case, output one line containing

`Case #xx: yy`

, where xx is the test case number (starting from 1) and yy is the minimum number of cuts.## Limits

Time limit: 10 seconds.

Memory limit: 1 GB.

1≤T≤1001≤T≤100.

1≤r1≤r2≤R1≤r1≤r2≤R.

1≤c1≤c2≤C1≤c1≤c2≤C.## Test Set 1

1≤R,C≤1001≤R,C≤100.

K=1K=1.## Test Set 2

1≤R,C≤1051≤R,C≤105.

1≤K≤1051≤K≤105.## Sample

Note: there are additional samples that are not run on submissions down below.Sample Input1 3 3 1 2 2 2 2Sample OutputCase #1: 5## Additional Sample – Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.Sample Input1 2 3 4 2 1 2 2Sample OutputCase #1: 3In the Sample Case, the minimum number of cuts is 55. One of the possible series of cuts is as follows:

In the Additional Sample Case, the minimum number of cuts is 33. One of the possible series of cuts is as follows:

## Solution: Click here