Birthday Cake solution kickstart
You are given a grid ofrows and columns that corresponds to a birthday cake.
The rows are numbered from to starting from the top. The columns are numbered from to starting from the left. Each cell in the grid is a square of size .
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 . 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 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.
- 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 thesides 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. 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).
- In the second picture, the cut starts from an unexposed point (neither one of thesides 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.
- 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.
The first line of the input gives the number of test cases,. test cases follow.
Each test case starts with a line containing three integers,, and .
The next line contains four integers, , , , , representing the top-left and bottom-right cell of the delicious rectangle respectively.
For each test case, output one line containing
Case #, where : is the test case number (starting from 1) and is the minimum number of cuts.
Time limit: 10 seconds.
Memory limit: 1 GB.
Test Set 1
Test Set 2
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: 3
In the Sample Case, the minimum number of cuts is. One of the possible series of cuts is as follows:
In the Additional Sample Case, the minimum number of cuts is. One of the possible series of cuts is as follows:
Solution: Click here