[codeforces] 1150B. Tiling Challenge

문제

https://codeforces.com/contest/1150/problem/B

Problem - B - Codeforces

 

풀이

왼쪽 위부터 순서대로 채운다. 이렇게 채워도 가능한 모든 경우를 다 볼수 있다는 것이 증명 가능하다.

 

#	#	#	#	#
#	ㅇ
ㅇ	ㅇ	ㅇ
	ㅇ

저 첫 빈칸을 채우기 위해서는 저 첫 빈칸을 위쪽타일로 하는 십자타일을 놓는 경우 외에는 존재하지 않는다.

따라서, 이 타일을 전부 채울수 있는 경우가 있다면, 저 곳은 o로 포함된 타일 모양으로 채워야 하고, 이를 반복적으로 진행하여, 다 채울 수 있는지 확인한다.

 

Time Complexity : $O(n^2)$

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define N 52
using namespace std;

int n;
string mp[N];
bool f(int p,int q)
{
	if(p<0 || q<0 || p>=n || q>=n) return false;
	return mp[p][q]=='.';
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>mp[i];

	for(int i=0;i<n*n;i++)
	{
		if(mp[i/n][i%n]=='#')continue;
		int x=i/n, y=i%n;
		if( !f(x,y) || !f(x+1, y-1) || !f(x+1, y) || !f(x+1, y+1) || !f(x+2, y))
		{
			cout<<"NO";
			return 0;
		}
		mp[x][y]=mp[x+1][y-1]=mp[x+1][y]=mp[x+1][y+1]=mp[x+2][y]='#';
	}
	cout<<"YES";
}