前言

這題題目實在有夠長，光題目我就看了非常久，題目看不懂真的很慘連做都沒辦法做(翻譯我也看不懂，中英文都很差真的很慘..)，還好最後多虧這位大大的文章和測試工具的幫忙才了解題目....。
原題目

題目

Code Jam團隊買了一個果園，他剛好是一個二維矩陣1000行和1000列，計畫用來種植各種樹木。

• 我們至少要有一個準備好的位置。
• 所有準備好的位置都必須組成一個對齊的矩形，矩形中每個位置也必須準備好。

注意，上述還包括已準備好的位置不能超過該矩形之外。
例如(＊為準備好位置, ．為未準備好位置):

當A = 11，如圖一雖然他面積是11但矩形內有一個未準備，那這個果園就不算是準備好，必須和圖二一樣整個矩形都準備好。

＊＊＊＊＊
＊．＊＊＊
＊＊＊＊＊
圖一

＊＊＊＊＊
＊＊＊＊＊
＊＊＊＊＊
圖二

當A = 6，如圖三很明顯未準備好，圖四雖然有6塊但它不是一個完整的矩形，圖五雖然有一個完整矩形但它周圍多出一塊已準備好，所以這些果園都未準備好。

＊＊
．＊
＊＊
圖三

．＊＊
＊．＊
．＊＊
圖四

．＊＊
＊＊＊
．＊＊
圖五

我們借用了Go gopher，指定位置來幫助我們，但我們還沒有完善的開發，目前只可以在指定位置為中心3X3區塊中隨機準備好一個位置。
我們只能使用1000次來完成我們的果園。

輸入輸出

這題是互動式題目，官方提供了下載Python腳本來進行測試，輸入整數T表示測試數量，A為矩形面積，最多只能互動1000次。
你的程式必須輸出ｉ和ｊ位置(中心位置)，並介於2~999之間，如果格式錯誤將會讀取到-1 -1已準備好位置。為了要回應請將程式使用標準輸入讀取回傳已準備好數值。
當你完成矩形則會接收到0 0位置，然後就停止輸入輸出，若程式還在等待則會判斷為超時。

範圍

1 ≤ T ≤ 20.
記憶體: 1 GB.

測試1:
A = 20.
時間限制: 20 秒.

測試2:
A = 200.
時間限制: 60 秒.

範例

t = readline_int() // 讀取T測資數量
a = readline_int() // 讀取A面積
printline 10 10 to stdout // 輸出10 10位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置10 11
printline 10 10 to stdout // 輸出10 10位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置10 10
printline 10 12 to stdout // 輸出10 12位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置10 11
printline 10 10 to stdout // 輸出10 10位置
flush stdout
x, y = readline_two_int() // 讀取到已準備好位置11 10
printline 11 10 to stdout // 輸出11 10位置
flush stdout
x, y = readline_two_int() // 讀取到0 0，已完成面積矩形

解析

當下看到題目非常之長，最後才發現其實就只是要你在1000次內把指定面積矩形做出來就好，測試固定20和200那問題就簡單許多了。

1. Go Gopher是隨機我們輸出的位置當中心來回傳的，那我們就可以先把固定一塊Block(3X3)填滿再去填滿下一塊，因為最大200塊也不用擔心會超出範圍。

測試工具

Windows cmd:testing_tool.py ./Console.exe
如果運行過會這樣

完整程式碼

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

using namespace std;

const int MAX = 1000;

void Process(const int& blockSize)
{
	vector<int> blockUsed(blockSize, 0);
	vector<vector<vector<bool>>> check(blockSize, vector<vector<bool>>(3, vector<bool>(3, true)));

	int index = 0;
	int count = 0;
	int centerX = 3;
	int centerY = 3;
	int x = 0;
	int y = 0;

	while (count < MAX) {
		cout << centerX << " " << centerY << endl;
		cin >> x >> y;

		if ((x == 0 && y == 0))
		{
			return;
		}

		const int offsetX = x - centerX + 1;
		const int offsetY = y - centerY + 1;

		if (check[index][offsetX][offsetY])
		{
			blockUsed[index] += 1;
			check[index][offsetX][offsetY] = false;
		}

		if (blockUsed[index] == 9)
		{
			index++;
			centerX += 3;
		}

		count++;
	}
}

void Input()
{
	int count = 0;

	if (cin >> count)
	{
		for (int index = 0; index < count; index++)
		{
			int area = 0;
			cin >> area;

			const int blockSize = (area / 9) + ((area % 9) == 0 ? 0 : 1);
			Process(blockSize);
		}
	}
}

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

程式碼解析

輸入

1.count 測資數量。
2.area 面積。
3.blockSize 3X3的Block數量。
4.Process 運行交互式函數。
5.開始交換訊息。

void Input()
{
	int count = 0;

	if (cin >> count)
	{
		for (int index = 0; index < count; index++)
		{
			int area = 0;
			cin >> area;

			const int blockSize = (area / 9) + ((area % 9) == 0 ? 0 : 1);
			Process(blockSize);
		}
	}
}

運行

1.我們先宣告一個容器blockUsed來記錄準備好的數量，和一個容器check來紀錄已準備好的位置(都是3X3當作一個index)。
2.index記錄目前Block位置，count來記錄交換次數(最大1000)。
3.我選擇從centerX = 3,centerY = 3當第一個Block的中心。
4.x和y則是要接收Go Gopher回傳已準備好的位置。

void Process(const int& blockSize)
{
	vector<int> blockUsed(blockSize, 0);
	vector<vector<vector<bool>>> check(blockSize, vector<vector<bool>>(3, vector<bool>(3, true)));

	int index = 0;
	int count = 0;
	int centerX = 3;
	int centerY = 3;
	int x = 0;
	int y = 0;

	while (count < MAX) {
		cout << centerX << " " << centerY << endl;
		cin >> x >> y;
        
        // 如果已完成則退出
		if ((x == 0 && y == 0))
		{
			return;
		}
        
        // 計算容器位置(可改為宣告1000 * 1000則不用計算)
		const int offsetX = x - centerX + 1;
		const int offsetY = y - centerY + 1;
        
        // 如果未使用，Block數量加一和設定已使用
		if (check[index][offsetX][offsetY])
		{
			blockUsed[index] += 1;
			check[index][offsetX][offsetY] = false;
		}
         
        // 當下Block已準備好，換下一塊
		if (blockUsed[index] == 9)
		{
			index++;
			centerX += 3;
		}

		count++;
	}
}

結語

這次改了一下解釋風格，但還是有部分式寫在裡面，會慢慢改善排版模式讓人輕鬆觀看。