|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|10 초 (추가 시간 없음)||1024 MB (추가 메모리 없음)||2||2||2||100.000%|
You are given a grid of R rows and C columns that corresponds to a birthday cake.
The rows are numbered from 1 to R starting from the top. The columns are numbered from 1 to C starting from the left. Each cell in the grid is a square of size 1×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 K.
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.
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 4 directions (up, down, left, right).
A cut is a directed line segment which is valid if the following conditions are met:
Suppose that K=4. Below you can find five examples of valid cuts.
And here are four examples of invalid cuts
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, T. T test cases follow.
Each test case starts with a line containing three integers, R, C and K.
The next line contains four integers, r1, c1, r2, c2, representing the top-left and bottom-right cell of the delicious rectangle respectively.
For each test case, output one line containing
Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of cuts.
1 3 3 1 2 2 2 2
Case #1: 5
1 2 3 4 2 1 2 2
Case #1: 3
In the Sample 1, the minimum number of cuts is 5. One of the possible series of cuts is as follows:
In the Sample 2, the minimum number of cuts is 3. One of the possible series of cuts is as follows: