IOI 2017 Nowruz

IOI 2017 Nowruz는 output only 문제로, 코드를 실행해서 나온 결과를 제출하면 되는 종류의 문제이다.

문제를 요약하자면, 몇몇 칸이 막혀 있는 격자가 있을 때, 뚫려 있는 칸들만을 사용해서 리프의 수가 가장 많은 트리를 만들어 내면 되는 문제이다. 전부 뚫려 있는 입력 몇 개와, 적절히 장애물이 있는 입력 몇 개가 있다.

내 접근은 다음과 같다. 리프의 수가 가장 많은 트리를 만드는 가장 좋은 방법 중 하나는, 기존의 트리에 포함되어 있지 않은 정점 중 포함시켰을 때 리프가 되는 정점을 포함시키는 것이다. 장애물이 많지 않으므로, 잘못 리프를 넣어 망칠 확률도 적다. 이러기 위해서는, 한 정점을 시작점으로 잡은 뒤 모든 격자를 돌아보면서 리프가 될수 있는 정점을 찾은 뒤 리프로 만들어주는 과정을 반복해주면 된다. 이를 100번 정도 반복시킨 뒤 최댓값을 구하면 80점 정도의 정답을 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <time.h>
#pragma warning(disable:4996)
using namespace std;
vector<string>arr;
int N, M;
int poss(int a, int b)
{
	if (a < 0 || b < 0 || a >= N || b >= M)
		return 0;
	return arr[a][b] == '.';
}
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int main()
{
	freopen("10.in", "r", stdin);
	int K;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> K;
	int i,j,k;
	vector<pair<int, int>>lis;
	srand(time(NULL));
	for (i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		for (j = 0; j < M; j++)
		{
			if (s[j] == '.')
				s[j] = 'X';
			lis.push_back({ i,j });
		}
		arr.push_back(s);
	}			

	auto oldarr = arr;
	pair<int, vector<string>>an;
	an.first = 0;
	for (i = 0; i < 10; i++)
	{
		arr = oldarr;
		int r1 = rand() % N;
		int r2 = rand() % M;
		while (arr[r1][r2] != 'X')
		{
			r1 = rand() % N;
			r2 = rand() % M;
		}
		arr[r1][r2] = '.';
		int tot = 1;
		while (1)
		{
			
			int ch = 0;
			int m;
			for (m = 0; m < N * M; m++)
			{
				j = lis[m].first;
				k = lis[m].second;
				if (arr[j][k] != 'X')
					continue;
				int c = 0;
				int l;
				for (l = 0; l < 4; l++)
				{
					c += poss(j + dx[l], k + dy[l]);
				}
				if (c == 1)
				{
					arr[j][k] = '.';
					ch++;
					tot++;
				}
			}
			if (!ch)
				break;
		}
		tot = 0;
		int m;
		for (m = 0; m < N * M; m++)
		{
			j = lis[m].first;
			k = lis[m].second;
			if (arr[j][k] != '.')
				continue;
			int c = 0;
			int l;
			for (l = 0; l < 4; l++)
			{
				c += poss(j + dx[l], k + dy[l]);
			}
			if (c == 1)
			{
				tot++;
			}
		}
		cerr << tot<<'\n';
		an = max(an, { tot,arr });
	}
	freopen("10.out", "w", stdout);
	for (i = 0; i < N; i++)
	{
		cout << an.second[i] << '\n';
	}
}