這題看到的時候很天真的直接切水平判斷,再切垂直判斷,結果當然是連下面測資都過不了,因為少判斷每個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);
}
}
}
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]++;
}
}
}
}
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;
}
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;
}
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;
}
這次打文章有點慘不小心按到上一頁,還好沒有多,真的有事沒事就要案儲存草稿,歡迎大家發布各種解法,讓別人參考也可以記錄自己一舉兩得。