iT邦幫忙

5

[Google Code Jam] C++ Waffle Choppers 華夫切餅機

前言

這題看到的時候很天真的直接切水平判斷,再切垂直判斷,結果當然是連下面測資都過不了,因為少判斷每個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;
}

結語

這次打文章有點慘不小心按到上一頁,還好沒有多,真的有事沒事就要案儲存草稿,歡迎大家發布各種解法,讓別人參考也可以記錄自己一舉兩得。


尚未有邦友留言

立即登入留言