[Brute Force] 십자가 찾기

예제 입력 1

6 8

....*...

...**...

..*****.

...**...

....*...

........

예제 출력 1

3

3 4 1

3 5 2

3 5 1

예제 입력 2

5 5

.*...

****.

.****

..**.

.....

예제 출력 2

3

2 2 1

3 3 1

3 4 1

예제 입력 3

5 5

.*...

***..

.*...

.*...

.....

예제 출력 3

-1

예제 입력 4

3 3 *.* .*. *.*

예제 출력 4

-1

 

- 맵을 돌면서, *이면 십자가 크기를 점점 늘려가며 만들기를 시도하는식으로 접근했다.

- 문제의 출력 조건에, "필요한 십자가의 수 k"는 0부터라고 되어있어서 빈칸(전부 .)로 넣으면 0만 출력하도록 구현했는데 다행히 정답

#include <stdio.h>

constexpr int MAX_VECTOR_SIZE = 10000;
constexpr int MAX_SIZE = 101;

int R, C;
char map[MAX_SIZE + 1][MAX_SIZE + 1];
char makeMap[MAX_SIZE + 1][MAX_SIZE + 1];

int dR[4] = { -1, 1, 0, 0 };
int dC[4] = { 0, 0, -1, 1 };

class cross
{
public:
	int r;
	int c;
	int size;

	cross() { r = c = size = 0; }
	cross(int r, int c, int size) : r(r), c(c), size(size) {}

	void printLine()
	{
		printf("%d %d %d\n", r+1, c+1, size);
	}
};

template <typename T>
class vector
{
public:
	T data[MAX_VECTOR_SIZE];
	int size;

	vector() { size = 0; }

	void push(T item)
	{
		data[size++] = item;
	}

	bool IsFull()
	{
		return size == MAX_VECTOR_SIZE;
	}
};
vector<cross> v;

bool IsInBoundary(int r, int c)
{
	return (r >= 0) && (r < R) && (c >= 0) && (c < C);
}

cross MakeMaxCross(int r, int c)
{
	cross crr(r,c,0);
	int i = 1;

	for (; ; i++)
	{
		bool isValidCross = true;

		for (int k = 0; k < 4; k++)
		{
			int nowR = r + (dR[k]*i);
			int nowC = c + (dC[k]*i);

			if (!IsInBoundary(nowR, nowC)) isValidCross = false;
			if (map[nowR][nowC] != '*') isValidCross = false;
		}

		if (!isValidCross) break;
	}

	crr.size = i - 1;

	if (crr.size > 0)
	{
		makeMap[r][c] = '*';

		for (int i = 1; i <= crr.size; i++)
		{
			for (int k = 0; k < 4; k++)
			{
				int nowR = r + (dR[k] * i);
				int nowC = c + (dC[k] * i);

				makeMap[nowR][nowC] = '*';
			}
		}
	}

	return crr;
}

bool go()
{
	for (int i = 1; i < R - 1; i++)
	{
		for (int j = 1; j < C - 1; j++)
		{
			if (map[i][j] == '*')
			{
				cross crr = MakeMaxCross(i, j);

				if (crr.size > 0)
				{
					if (v.IsFull()) return false;
					v.push(crr);
				}
			}
		}
	}

	return true;
}

bool compare()
{
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			if (map[i][j] != makeMap[i][j]) 
				return false;
 		}
	}
	
	return true;
}

int main(void)
{
	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			char input = '\n';

			while (input == '\n')
			{
				scanf("%c", &input);
			}
			
			map[i][j] = input;
			makeMap[i][j] = '.';
		}
	}
	
	if (!go())
	{
		printf("-1\n");
		return 0;
	}

	if (compare())
	{
		printf("%d\n", v.size);
		for (int i = 0; i < v.size; i++)
		{
			v.data[i].printLine();
		}
	}
	else
	{
		printf("-1\n");
		return 0;
	}

	return 0;
}