Решение задачи "Заполнение квадратов" с Codeforces

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

Вам заданы две матрицы A и B. В каждой матрице ровно n строк и m столбцов. Каждый элемент A — 0 или 1; каждый элемент B изначально равен 0.

Вы можете провести любое количество операций с матрицей B. Для проведения операции вы должны выбрать любую подматрицу B размера 2×2 и заменить все элементы в этой подматрице на 1. Иными словами, вы выбираете два целых числа x и y (1≤x
Ваша задача — сделать матрицу B равной матрице A. Две матрицы A и B равны тогда и только тогда, когда каждый элемент матрицы A равен соответствующему элементу матрицы B.

Можно ли сделать матрицы равными? Если это так, вы должны найти последовательность операций, которые делают матрицу B равной матрице A. Обратите внимание, что минимизировать количество операций не нужно.

Код 

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 55;
int n, m, a[MAXN][MAXN], b[MAXN][MAXN];
vector<pair<int, int>> ans;

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1, j; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			scanf("%d", &a[i][j]);
	for(int i = 1, j; i < n; ++i)
		for(j = 1; j < m; ++j)
		{
			if(a[i][j] && a[i + 1][j] && a[i][j + 1] && a[i + 1][j + 1])
			{
				ans.emplace_back(i, j);
				b[i][j] = b[i + 1][j] = b[i][j + 1] = b[i + 1][j + 1] = 1;
			}
		}
	for(int i = 1, j; i <= n; ++i)
		for(j = 1; j <= m; ++j)
			if(a[i][j] != b[i][j])
				printf("-1\n"), exit(0);
	printf("%d\n", ans.size());
	for(const auto&[x, y] : ans)
		printf("%d %d\n", x, y);
}

         

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


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

Комментарии

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