[Solution] Birthday Cake solution kickstart

 Birthday Cake solution kickstart


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 kickstart

We 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.

 Birthday Cake solution kickstartAnd here are four examples of invalid cuts

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, TTTT test cases follow.

Each test case starts with a line containing three integers, RRCC and KK.
The next line contains four integers, r1r1c1c1r2r2c2c2, representing the top-left and bottom-right cell of the delicious rectangle respectively.

Output

For each test case, output one line containing Case #xxyy, 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.
1T1001≤T≤100.
1r1r2R1≤r1≤r2≤R.
1c1c2C1≤c1≤c2≤C.

Test Set 1

1R,C1001≤R,C≤100.
K=1K=1.

Test Set 2

1R,C1051≤R,C≤105.
1K1051≤K≤105.

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input
content_copy
1
3 3 1
2 2 2 2
Sample Output
content_copy
Case #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 Input
content_copy
1
2 3 4
2 1 2 2
Sample Output
content_copy
Case #1: 3

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

Visualization for the first sample case, showing 5 cuts.In the Additional Sample Case, the minimum number of cuts is 33. One of the possible series of cuts is as follows:

Visualization for the second sample case, showing 3 cuts.


Solution: Click here

 

Leave a Comment