Untitled

mail@pastecode.io avatar
unknown
plain_text
16 days ago
2.8 kB
0
Indexable
Never
Turn Over Game
As in , there is a 4×4 sized table. In a grid of the table, there are white or black stones. When you choose a position of stone randomly, the stone and four stones adjacent to the up, down, left and right sides of the stone will turn to the opposite color like turning a white stone to a black & a black stone to a white. Let’s suppose this process as a calculation.


Using such a calculation, you want to change all the stones on the table into all whites or all blacks. Find out the minimum operation count at this time.

Time limit: 1 second (java: 2 seconds)

[Input]
Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T (T ≤ 30) are given in a row.
Table info is given without blank over four rows per each test case. Colors are indicated like white for ‘w’ and black for ‘b’.

[Output]
Output the minimum operation count to change all colors as white or black on the first row per each test case. If not possible, output "impossible" .

[I/O Example]
Input
2
bwwb
bbwb
bwwb
bwww
bwbw
wwww
bbwb
bwwb

Output
Case #1 

4 

Case #2
impossible


#include <iostream>
using namespace std;

int oTrang, oDen, demLuot, minLuot;
char arr[4][4];
int nhiPhan[4][4];

int dx[] = {0, -1, 0, 1, 0};
int dy[] = {0, 0, 1, 0, -1};

void latNguoc(int x, int y) {
	for (int i = 0; i < 5; i++)
	{
		int newX = x + dx[i];
		int newY = y + dy[i];

		if (newX >= 0 && newX < 4 && newY >= 0 && newY < 4)
		{
			if (arr[newX][newY] == 'b')
			{
				oDen--;
				oTrang++;
				arr[newX][newY] = 'w';
			}
			else
			{
				oTrang--;
				oDen++;
				arr[newX][newY] = 'b';
			}
		}
	}
}

void dayNhiPhan(int index) {
	if (oTrang == 16 || oDen == 16)
	{
		if (minLuot > demLuot)
		{
			minLuot = demLuot;
		}
	}

	if (index == 16)
		return;
	int row = index / 4;
	int col = index % 4;

	nhiPhan[row][col] = 1;
	//lam
	latNguoc(row, col);
	demLuot++;
	dayNhiPhan(index + 1);

	//khong lam gi
	nhiPhan[row][col] = 0;
	latNguoc(row, col);
	demLuot--;
	dayNhiPhan(index + 1);
}

int main() {
	//freopen("Text.txt", "r", stdin);

	int T;
	cin >> T;

	for (int tc = 1; tc <= T; tc++)
	{
		oTrang = 0;
		oDen = 0;
		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j < 4; j++)
			{
				cin >> arr[i][j];
				if (arr[i][j] == 'b')
				{
					oDen++;
				}
				else
				{
					oTrang++;
				}
			}
		}

		demLuot = 0;
		minLuot = 1e8;
		int index = 0;

		dayNhiPhan(0);

		if (minLuot == 1e8)
		{
			cout << "Case #" << tc << endl;
			cout << "impossible" << endl;
		}
		else
		{
			cout << "Case #" << tc << endl;
			cout << minLuot << endl;
		}
	}

	return 0;
}
Leave a Comment