5

1 <= Ť <= 100 。

2 ≤ R ≤ 10.
2 ≤ C ≤ 10.
H = 1.
V = 1.

2 ≤ R ≤ 100.
2 ≤ C ≤ 100.
1 ≤ H < R.
1 ≤ V < C.

# 範例

6
3 6 1 1
.@@..@
.....@
@.@.@@
4 3 1 1
@@@
@.@
@.@
@@@
4 5 1 1
.....
.....
.....
.....
4 4 1 1
..@@
..@@
@@..
@@..
3 4 2 2
@.@@
@@.@
@.@@
3 4 1 2
.@.@
@.@.
.@.@

### 輸出

Case #1: POSSIBLE
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
Case #4: IMPOSSIBLE
Case #5: POSSIBLE
Case #6: IMPOSSIBLE

# 分析

1.我們首先可以知道切一刀可分成兩塊，兩刀可切成四塊，那我們就可以先算水平的再算垂直的，是否我們切的碎片裡面巧克力是相等的。

``````@.@@
@@.@
@.@@
``````

``````@　.@　@
@　@.　@
@　.@　@
``````

``````@.@@

@@.@

@.@@
``````

2.然後做第一步是不夠的，當你遇到如下圖就不會過了，這時候我們就必須得取我們水平和垂直切割的位置，在去計算每塊的巧克力是否是等於平均巧克力。

``````..　@@
..　@@

@@　..
@@　..
``````

# 完整程式碼

``````#include <iostream>
#include <string>
#include <vector>

using namespace std;

void SetChocolate(const vector<string>& coockie
, int& tChocolate, vector<int>& hChocolate, vector<int>& vChocolate)
{

for (size_t row = 0; row < coockie.size(); row++)
{
for (size_t col = 0; col < coockie[0].size(); col++)
{
if (coockie[row][col] == '@')
{
tChocolate++;
vChocolate[col]++;
hChocolate[row]++;
}
}
}
}

int GetSplitChocolate(const vector<string>& coockie
, const int& sRow, const int& eRow
, const int& sCol, const int& eCol)
{
int sum = 0;

for (int row = sRow; row <= eRow; row++)
{
for (int col = sCol; col <= eCol; col++)
{
if (coockie[row][col] == '@')
{
sum++;
}
}
}
return sum;
}

vector<int> GetLine(const vector<int>& chocolate, const int& needChocolate, const int& splitSize)
{
vector<int> splitLine(splitSize);
int sum = 0;
int count = 0;
size_t index = 0;
while (index < chocolate.size())
{
sum += chocolate[index];
if (sum == needChocolate)
{
splitLine[count] = index;
count++;
sum = 0;
}
index++;
}

if (count != splitSize)
{
splitLine[0] = -1;
}
return splitLine;
}

bool Process(const vector<string>& coockie
, const int& hSplit, const int& vSplit)
{
int totalChocolate = 0;
vector<int> hChocolate(coockie.size(), 0);
vector<int> vChocolate(coockie[0].size(), 0);

SetChocolate(coockie, totalChocolate, hChocolate, vChocolate);

if (totalChocolate == 0)
{
return true;
}

const int hSize = hSplit + 1;
const int vSize = vSplit + 1;

if (totalChocolate % (hSize * vSize) != 0)
{
return false;
}

const int cookieSize = totalChocolate / (hSize * vSize);
const int hNeed = totalChocolate / hSize;
const int vNeed = totalChocolate / vSize;

const vector<int> hLine = GetLine(hChocolate, hNeed, hSize);

if (hLine[0] == -1)
{
return false;
}

const vector<int> vLine = GetLine(vChocolate, vNeed, vSize);

if (vLine[0] == -1)
{
return false;
}

int lastRow = -1;

for (size_t row = 0; row < hLine.size(); row++)
{
int lastCol = -1;

for (size_t col = 0; col < vLine.size(); col++)
{
int count = GetSplitChocolate(coockie
, lastRow + 1, hLine[row]
, lastCol + 1, vLine[col]);

if (count != cookieSize)
{
return false;
}
lastCol = vLine[col];
}
lastRow = hLine[row];
}

return true;
}

void Print(const int& index, const bool& result)
{
if (result)
{
cout << "Case #" << index + 1 << ": POSSIBLE" << endl;
}
else
{
cout << "Case #" << index + 1 << ": IMPOSSIBLE" << endl;
}
}

void Input()
{
int count = 0;
if (cin >> count)
{
for (int index = 0; index < count; index++)
{
int rowSize = 0;
int colSize = 0;
int hSplit = 0;
int vSplit = 0;

cin >> rowSize >> colSize >> hSplit >> vSplit;

vector<string> coockie(rowSize);
for (int row = 0; row < rowSize; row++)
{
cin >> coockie[row];
}

bool result = Process(coockie, hSplit, vSplit);

Print(index, result);
}
}
}

int main()
{
Input();
return 0;
}
``````

# 程式碼解析

### 輸入輸出流程

1.count測試資料T筆數。
2.rowSize為R餅乾水平數量。
3.colSize為C餅乾垂直數量。
5.hSplit為H水平切割次數。
6.vSplit為V垂直切割次數。
7.開始輸入餅乾字符。
8.Process傳入字符判斷是否會達成目標。
9.Print輸出結果。

``````void Input()
{
int count = 0;
if (cin >> count)
{
for (int index = 0; index < count; index++)
{
int rowSize = 0;
int colSize = 0;
int hSplit = 0;
int vSplit = 0;

cin >> rowSize >> colSize >> hSplit >> vSplit;

vector<string> coockie(rowSize);
for (int row = 0; row < rowSize; row++)
{
cin >> coockie[row];
}

bool result = Process(coockie, hSplit, vSplit);

Print(index, result);
}
}
}
``````

### 函數介紹

• SetChocolate
coockie: 餅乾字符
tChocolate: 餅乾擁有巧克力總數量
hChocolate: 每個水平擁有巧克力的數量
vChocolate: 每個垂直擁有巧克力的數量
主要用來初始化設定我們所要的資訊，方便計算。
1.走訪每個字符紀錄巧克力總數量.水平巧克力總數.垂直巧克力總數。
``````void SetChocolate(const vector<string>& coockie
, int& tChocolate, vector<int>& hChocolate, vector<int>& vChocolate)
{

for (size_t row = 0; row < coockie.size(); row++)
{
for (size_t col = 0; col < coockie[0].size(); col++)
{
if (coockie[row][col] == '@')
{
tChocolate++;
vChocolate[col]++;
hChocolate[row]++;
}
}
}
}
``````
• GetLine
chocolate: 垂直或水平巧克力總數
needChocolate: 每塊所需的巧克力數量
splitSize: 切割的數量
用來得取水平或垂直分割線的索引值位置，若無法切割(切割完小於切割數量)回傳-1。
1.走訪每一個水平(行)或垂直(列)的巧克力數量(初始化計算的)。
2.用一個暫存計算目前巧克力數量。
3.若暫存數量已達到我們所需數量，即可將已切割數量加一，直到走訪完。
4.若已切割數量小於我們要的切割數量代表無法切割回傳-1，反之回傳全部正確索引位置。
``````vector<int> GetLine(const vector<int>& chocolate
, const int& needChocolate, const int& splitSize)
{
vector<int> splitLine(splitSize);
int sum = 0;
int count = 0;
size_t index = 0;
while (index < chocolate.size())
{
sum += chocolate[index];
if (sum == needChocolate)
{
splitLine[count] = index;
count++;
sum = 0;
}
index++;
}

if (count != splitSize)
{
splitLine[0] = -1;
}
return splitLine;
}
``````
• GetSplitChocolate
coockie:輸入的餅乾字符
sRow:計算垂直的起始索引值
eRow:計算垂直的結束索引值
sCol:計算水平的起始索引值
eCol:計算水平的結束索引值
主要用來計算一個區塊所擁有的餅乾數量。
1.走訪coockie起始位置[sRow, sCo]l, 結束位置[eRow, eCol]，若等於'@'則數量加一。
``````int GetSplitChocolate(const vector<string>& coockie
, const int& sRow, const int& eRow
, const int& sCol, const int& eCol)
{
int sum = 0;

for (int row = sRow; row <= eRow; row++)
{
for (int col = sCol; col <= eCol; col++)
{
if (coockie[row][col] == '@')
{
sum++;
}
}
}
return sum;
}
``````
• Process
coockie: 輸入的餅乾字符
hSplit:切割水平次數
vSplit:切割垂直次數
1.SetChocolate初始化總數量.垂直數量.水平數量。
2.totalChocolate == 0無巧克力所以直接回傳true。
2.hSize.vSize為水平和傳直切割的"塊數"。
3.巧克力總數若無法整除全部塊數那就是無法切割。
4.cookieSize水平垂直兩個切割好後的每一區塊需要的巧克力數量。
5.hNeed, vNeed水平和垂直每塊所需要的巧克力數量。
6.GetLine得取水平和垂直的全部索引位置，若無法切割則回傳false。
7.開始走訪我們剛剛得取的水平和垂直的的位置，GetSplitChocolate去計算每一塊所需數量。
8.若數量不是正確分割數量(cookieSize)，則回傳false，走訪完則回傳true。
``````bool Process(const vector<string>& coockie, const int& hSplit, const int& vSplit)
{
int totalChocolate = 0;
vector<int> hChocolate(coockie.size(), 0);
vector<int> vChocolate(coockie[0].size(), 0);

SetChocolate(coockie, totalChocolate, hChocolate, vChocolate);

if (totalChocolate == 0)
{
return true;
}

const int hSize = hSplit + 1;
const int vSize = vSplit + 1;

if (totalChocolate % (hSize * vSize) != 0)
{
return false;
}

const int cookieSize = totalChocolate / (hSize * vSize);
const int hNeed = totalChocolate / hSize;
const int vNeed = totalChocolate / vSize;

const vector<int> hLine = GetLine(hChocolate, hNeed, hSize);

if (hLine[0] == -1)
{
return false;
}

const vector<int> vLine = GetLine(vChocolate, vNeed, vSize);

if (vLine[0] == -1)
{
return false;
}

int lastRow = -1;

for (size_t row = 0; row < hLine.size(); row++)
{
int lastCol = -1;

for (size_t col = 0; col < vLine.size(); col++)
{
int count = GetSplitChocolate(coockie,
lastRow + 1, hLine[row]
, lastCol + 1, vLine[col]);

if (count != cookieSize)
{
return false;
}
lastCol = vLine[col];
}
lastRow = hLine[row];
}

return true;
}
``````