quiz_0726

quiz.cpp

#include <iostream>
using namespace std;

int CalcAreaNum(bool **arrStage, int M, int N, int* l_m = nullptr, int* l_n = nullptr)
{
	int AreaNum = 0;

	bool **_arrStage = new bool*[M];

	// malloc
	for (int i = 0; i < M; ++i)
		_arrStage[i] = new bool[N];

	// init
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N; ++j)
			_arrStage[i][j] = false;

	bool nowWorkColor = false;
	// algorithm
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N; ++j)
		{
			if (!_arrStage[i][j])
			{
				// 만약 리스트가 존재한다면 리스트에 수를 넣는다
				if (l_m && l_n)
				{
					l_m[AreaNum] = i;
					l_n[AreaNum] = j;
				}

				// 빈 영역 최초 선택 시 횟수를 더한다
				AreaNum++;
				nowWorkColor = arrStage[i][j];

				// 이미 앞에서부터 검사하였으므로 최초 1회는 단방향으로만 검사
				for (int k = j; k < N && (arrStage[i][k] == nowWorkColor); ++k)
					_arrStage[i][k] = true;

				// 루프
				bool bAllClear = false;

				while (!bAllClear)
				{
					bAllClear = true;
					for (int k = 1; k < M; ++k)
					{
						for (int a = 0; a < N; ++a)
							if (!_arrStage[k][a] && _arrStage[k - 1][a] && arrStage[k - 1][a] == arrStage[k][a])
							{
								bAllClear = false;
								_arrStage[k][a] = true;
							}
						for (int a = 1; a < N; ++a)
							if (!_arrStage[k][a] && _arrStage[k][a - 1] && arrStage[k][a - 1] == arrStage[k][a])
							{
								bAllClear = false;
								_arrStage[k][a] = true;
							}

						for (int a = N - 2; a >= 0; --a)
							if (!_arrStage[k][a] && _arrStage[k][a + 1] && arrStage[k][a + 1] == arrStage[k][a])
							{
								bAllClear = false;
								_arrStage[k][a] = true;
							}

					}

					for (int k = M - 2; k >= 0; --k)
					{
						for (int a = 0; a < N; ++a)
							if (!_arrStage[k][a] && _arrStage[k + 1][a] && arrStage[k + 1][a] == arrStage[k][a])
							{
								bAllClear = false;
								_arrStage[k][a] = true;
							}

						for (int a = 1; a < N; ++a)
							if (!_arrStage[k][a] && _arrStage[k][a - 1] && arrStage[k][a - 1] == arrStage[k][a])
							{
								bAllClear = false;
								_arrStage[k][a] = true;
							}

						for (int a = N - 2; a >= 0; --a)
							if (!_arrStage[k][a] && _arrStage[k][a + 1] && arrStage[k][a + 1] == arrStage[k][a])
							{
								bAllClear = false;
								_arrStage[k][a] = true;
							}

					}
				}

			}
		}

	// free
	for (int i = 0; i < M; ++i)
		delete[] _arrStage[i];
	delete[] _arrStage;

	return AreaNum;
}

void Overdraw(bool **arrStage, int M, int N, int s_m, int s_n)
{
	int nOverdraws = 0;
	bool **_overdraws = new bool*[M*N];

	bool **_arrStage = new bool*[M];

	// malloc
	for (int i = 0; i < M; ++i)
		_arrStage[i] = new bool[N];

	// init
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N; ++j)
			_arrStage[i][j] = false;

	bool nowWorkColor = false;
	// algorithm
	nowWorkColor = arrStage[s_m][s_n];

	// 이미 앞에서부터 검사하였으므로 최초 1회는 단방향으로만 검사
	for (int k = s_n; k < N && (arrStage[s_m][k] == nowWorkColor); ++k)
	{
		_overdraws[nOverdraws++] = &arrStage[s_m][k];
		_arrStage[s_m][k] = true;
	}

	// 루프
	bool bAllClear = false;

	while (!bAllClear)
	{
		bAllClear = true;

		for (int k = 1; k < M; ++k)
		{
			for (int a = 0; a < N; ++a)
				if (!_arrStage[k][a] && _arrStage[k - 1][a] && arrStage[k - 1][a] == arrStage[k][a])
				{
					bAllClear = false;
					_overdraws[nOverdraws++] = &arrStage[k][a];
					_arrStage[k][a] = true;
				}
			for (int a = 1; a < N; ++a)
				if (!_arrStage[k][a] && _arrStage[k][a - 1] && arrStage[k][a - 1] == arrStage[k][a])
				{
					bAllClear = false;
					_overdraws[nOverdraws++] = &arrStage[k][a];
					_arrStage[k][a] = true;
				}
			for (int a = N - 2; a >= 0; --a)
				if (!_arrStage[k][a] && _arrStage[k][a + 1] && arrStage[k][a + 1] == arrStage[k][a])
				{
					bAllClear = false;
					_overdraws[nOverdraws++] = &arrStage[k][a];
					_arrStage[k][a] = true;
				}
		}

		for (int k = M - 2; k >= 0; --k)
		{
			for (int a = 0; a < N; ++a)
				if (!_arrStage[k][a] && _arrStage[k + 1][a] && arrStage[k + 1][a] == arrStage[k][a])
				{
					bAllClear = false;
					_overdraws[nOverdraws++] = &arrStage[k][a];
					_arrStage[k][a] = true;
				}

			for (int a = 1; a < N; ++a)
				if (!_arrStage[k][a] && _arrStage[k][a - 1] && arrStage[k][a - 1] == arrStage[k][a])
				{
					bAllClear = false;
					_overdraws[nOverdraws++] = &arrStage[k][a];
					_arrStage[k][a] = true;
				}

			for (int a = N - 2; a >= 0; --a)
				if (!_arrStage[k][a] && _arrStage[k][a + 1] && arrStage[k][a + 1] == arrStage[k][a])
				{
					bAllClear = false;
					_overdraws[nOverdraws++] = &arrStage[k][a];
					_arrStage[k][a] = true;
				}

		}
	}

	for (int i = 0; i < nOverdraws; ++i)
		*_overdraws[i] = !nowWorkColor;

	// for Debug

	//for (int i = 0; i < M; ++i, cout << endl)
	//	for (int j = 0; j < N; ++j)
	//		(arrStage[i][j]) ? cout << "1 " : cout << "0 ";
	//cout << endl;

	// free
	for (int s_m = 0; s_m < M; ++s_m)
		delete[] _arrStage[s_m];
	delete[] _arrStage;
	delete[] _overdraws;
}

void CalcNextStep(bool **arrStage, int M, int N, int* r_m, int* r_n)
{
	bool **_arrStage = new bool*[M];

	// malloc
	for (int i = 0; i < M; ++i)
		_arrStage[i] = new bool[N];

	int* list_M = new int[M*N];
	int* list_N = new int[M*N];

	int Areanum = CalcAreaNum(arrStage, M, N, list_M, list_N);
	int nMin = Areanum;
	int nowNum;

	int M_Min;
	int N_Min;

	for (int i = 0; i < Areanum; ++i)
	{
		// init
		for (int i = 0; i < M; ++i)
			for (int j = 0; j < N; ++j)
				_arrStage[i][j] = arrStage[i][j];

		Overdraw(_arrStage, M, N, list_M[i], list_N[i]);

		nowNum = CalcAreaNum(_arrStage, M, N);
		if (nowNum < nMin)
		{
			nMin = nowNum;
			M_Min = list_M[i];
			N_Min = list_N[i];
		}

	}

	*r_m = M_Min;
	*r_n = N_Min;

	// free
	for (int i = 0; i < M; ++i)
		delete[] _arrStage[i];
	delete[] _arrStage;
	delete[] list_M;
	delete[] list_N;

}

int main()
{
	int nCount;
	cout << "test num : ";
		cin >> nCount;
	for (int itr = 0; itr < nCount; itr++)
	{

		cout << "test : " << (itr + 1) << endl;

		// 행과 열
		int M, N;
		cout << "input raw : ";
		cin >> M;
		cout << "input column : ";
		cin >> N;

		cout << endl;
		// 스테이지 세팅
		bool **arrStage = new bool*[M];
		for (int i = 0; i < M; ++i)
			arrStage[i] = new bool[N];

		for (int i = 0; i < M; ++i)
			for (int j = 0; j < N; ++j)
				arrStage[i][j] = (rand() % 2) ? true : false;

		for (int i = 0; i < M; ++i, cout << endl)
			for (int j = 0; j < N; ++j)
				(arrStage[i][j]) ? cout << "□" : cout << "■";
		cout << endl;

		// 최초에 존재하는 영역 개수
		cout << "num : " << CalcAreaNum(arrStage, M, N) << endl;
		cout << endl;

		int od_m;
		int od_n;
		int nCountLoop = 0;
		while (CalcAreaNum(arrStage, M, N) > 1)
		{
			CalcNextStep(arrStage, M, N, &od_m, &od_n);
			Overdraw(arrStage, M, N, od_m, od_n);
			nCountLoop++;
			cout << "count : " << nCountLoop << endl << endl;

			for (int i = 0; i < M; ++i, cout << endl)
				for (int j = 0; j < N; ++j)
					(arrStage[i][j]) ? cout << "□" : cout << "■";
			cout << endl;
		}

		cout << endl << endl << endl << "count : " << nCountLoop << endl;

		for (int i = 0; i < M; ++i, cout << endl)
			for (int j = 0; j < N; ++j)
				(arrStage[i][j]) ? cout << "□" : cout << "■";
		cout << endl;


		// 메모리 해제
		for (int i = 0; i < M; ++i)
			delete[] arrStage[i];
		delete[] arrStage;

//		cout << nCount << endl << M << " " << N << endl;
	}


}