16924번: 십자가 찾기

메모리

시간

5148 KB

52 ms

Code

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

char map[100][100];
int cross[100][100];
int result = 0;
vector <int> vec;
int ai[5] = {0, 1, -1, 0, 0};
int aj[5] = {0, 0, 0, 1, -1};

void	check_cross(int i, int j, int n, int m)
{
	int c = 1;
// 네 방향이 map 범위 안에 있고 *일때 십자가 카운트 및 좌표 저장.
	while (i - c >= 0 && i + c < n && j - c >= 0 && j + c < m)
	{
		if (map[i - c][j] == '*' && map[i + c][j] == '*' &&
			map[i][j + c] == '*' && map[i][j - c] == '*')
		{
			result++;
			for (int z = 0; z < 5; z++)
				cross[i + ai[z] * c][j + aj[z] * c] = 1;
			vec.push_back(i + 1);
			vec.push_back(j + 1);
			vec.push_back(c);
			c++;
		}
		else
			break;
	}
}

int main(int argc, char const *argv[])
{
	int n,m;
	cin >> n;
	cin >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == '*')
				check_cross(i, j, n, m);
		}
	}
//십자가에 포함되지 못한 *이 있을 시 -1출력 종료
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == '*' && cross[i][j] != 1)
			{
				printf("%d", -1);
				return 0;
			}
		}
	}
	int z = 0;
	printf("%d\\n", result);
	for (int i = 0; i < result; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			printf("%d ", vec[z]);
			z++;
		}
		printf("\\n");
	}
	return 0;
}

문제 풀이

문제는 주어진 맵에서 십자가를 찾아서 갯수와 좌표를 출력하는 문제이다 .이 빈칸 *이 십자가가 될 수 있는 문자이다.

십자가는 중복으로 카운트될 수 있고 십자가 모양이 없거나 십자가로 사용되지 않는 *이 있으면 -1을 출력한다.

우선 십자가가 될 수 있는 필수 조건으로 현재 좌표와 사방이 *일때를 찾아 한칸씩 네 방향으로 찾아가면서 카운트를 하였고 십자가로 확정(?)이 된 칸은 cross 배열에 1로 표시해주었다.

모든 맵을 체크하고 다시 모든 인덱스를 체크하면서 만약 map 배열이 *이고 cross 배열이 0이라면 -1로 종료하였다.