Решение задачи Испытание замощением с Codeforces

Без пояснения   Просмотров: 83

Однажды Алиса делала уборку в своем подвале и заметила кое-что любопытное: бесконечное множество одинаковых деревянных фигур! Каждая фигура была сделана из пяти квадратных плиток, одна из была центральной, а остальные четыре примыкали к ней:


Около кусочков лежала большая квадратная доска. Доска разделена на n2 клеток, расположенных в n строках и n столбцах. Некоторые клетки уже заняты плитками, прибитыми к клеткам. Остальные клетки свободны.

Алиса подумала, сможет ли она заполнить доску полностью, используя найденные фигуры? Конечно, каждая фигура должна покрывать ровно пять ячеек доски, никакие две фигуры не должны перекрываться и ни одна фигура не должна вылезать за пределы доски. Однако доска была слишком большой, и Алиса не смогла покрыть ее вручную. Можете ли вы помочь ей определить, возможно ли полностью покрыть доску фигурами?

Код 

#include <bits/stdc++.h>
using namespace std;
const int N = 63;
char s[N][N];
int n;
bool check(int x, int y)
{
	if (x < 0 || x >= n || y < 0 || y >= n || s[x][y] == '#')
		return 1;
	return s[x][y] = '#', 0;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%s", s[i]);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (s[i][j] != '#')
				if (check(i, j) || check(i + 1, j - 1) || check(i + 1, j) || check(i + 1, j + 1) || check(i + 2, j))
					return printf("NO"), 0;
	printf("YES");
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта