前言

这题看到的时候很天真的直接切水平判断，再切垂直判断，结果当然是连下面测资都过不了，因为少判断每个Block拥有
的饼乾数量，但庆幸不用重写，只要再多一个判断Block就好。

题目

有间煎饼餐厅的客人已经厌倦了圆形煎饼，所以厨师提供新的菜单选择：华夫饼！作为噱头，他们製作了一大个华夫饼乾，它有R行和C列网格。华夫饼每一个如果不是空的，就是含有一个巧克力片。
现在厨师在客人面前切割。一边切割水平线，一边切割垂直线。为了效率问题，让一个厨师切割H条水平线另一个厨师切割V条垂直线。这将每个(H + 1) x (V + 1)使用餐者方便拿取。这些碎片不一定有相同大小，但客人并不关心这一点。
客人关心的是他们获得的巧克力数量，因此每一碎片必须有相同的巧克力片。你能确定厨师是否可以使用给定的水平数量和垂直数量来实现切割目标？

输入

输入第一行T为测试比数; 每个开头都包含四个整数R、C、H和V:华夫饼乾的行数和列数，和厨师必须製作的水平和垂直切割的数量。然后有R行和C列的字符;代表第i个中的第j个字符表示华夫饼的第i行j列的位置。字符'@'代表有巧克片，字符'.'代表没有。

输出

输出每笔资料，包含Case #x: y，其中x是测试笔数编号从1开始()，如果厨师可完成目标y输出POSSIBLE，如果不能则输出IMPOSSIBLE。

範围

1 <= Ť <= 100 。
时间限制:6秒。
记忆体限制：1GB。

测资1:
2 ≤ R ≤ 10.
2 ≤ C ≤ 10.
H = 1.
V = 1.

测资2:
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.我们首先可以知道切一刀可分成两块，两刀可切成四块，那我们就可以先算水平的再算垂直的，是否我们切的碎片里面巧克力是相等的。
例如我们目前的饼为:

@.@@@@.@@.@@

水平切:如下图每块都是3个巧克力。

@　.@　@@　@.　@@　.@　@

垂直切:如下图每块都是3个巧克力。

@.@@@@.@@.@@

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;}

结语

这次打文章有点惨不小心按到上一页，还好没有多，真的有事没事就要案储存草稿，欢迎大家发布各种解法，让别人参考也可以记录自己一举两得。