MKJUMPS.cpp

#include <iostream>
using namespace std;

int n;              // Số hàng
int Answer;         // Đáp án
int sum;            // Tổng số lượng ô của bàn cờ
int Matrix[10][10]; // Lưu bàn cờ
int SR, SC;         // Tọa độ vị trí đầu tiên.

int drow[8] = {-2,-1,1,2, 2, 1,-1,-2};
int dcol[8] = { 1, 2,2,1,-1,-2,-2,-1};

void Start(int row, int col, int cnt)
{
	for(int i = 0; i < 8; i++)
	{
		int r = row + drow[i];
		int c = col + dcol[i];
		
		// Chỉ xét những ô thuộc bàn cờ và chưa được thăm
		// vì mỗi ô chỉ được đi qua một lần
		if(r >= 0 && r < n && c >= 0 && c < 10 && Matrix[r][c] == 1)
		{
			Matrix[r][c] = 2;
			Start(r, c, cnt+1);
			Matrix[r][c] = 1;
		}
	}
	
	// Cập nhật số lượng ô đi qua nhiều nhất
	if(cnt > Answer) Answer = cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);
	int tc = 0;
	while(true)
	{
		cin >> n;
		if(n == 0) break;
		
		tc++;
		Answer = sum = 0;
		for(int i = 0; i < 10; i++)
			for(int j = 0; j < 10; j++)
				Matrix[i][j] = 0;

		int zero, number;
		for(int i = 0; i < n; i++)
		{
			cin >> zero >> number;
			sum += number;
			
			// Lấy ra tọa độ ô đầu tiên
			if(i == 0)
			{
				SR = 0;
				SC = zero;
			}

			// Đánh dấu những ô thuộc bàn cờ là 1
			for(int j = 0; j < number; j++)
				Matrix[i][j + zero] = 1;
		}

		// Những ô đã đi qua đánh dấu là 2
		Matrix[SR][SC] = 2;
		Start(SR, SC, 1);

		Answer = sum - Answer;

		// output
		cout << "Case " << tc << ", " << Answer ;
		if (Answer == 1)  cout << " square can not be reached." << endl;
		else cout << " squares can not be reached." << endl;
	}
	return 0;
}