BOJ 17136-カラーペーパーの貼り付け

18714 ワード
boj テキストリンク
タイムアウトメモリ制限正解の送信正解正解正解正解率1秒512 MB 12934758235732.164%

質問する


図1に示すように、正方形の色紙が5種類あります.色紙の大きさは1×1, 2×2, 3×3, 4×4, 5×5は全部で5種類あり、カラーペーパーはそれぞれ5種類あります.

色のサイズは10×10人分の紙に貼る.紙は1×1つの大きさの格子に分けられ、各格子には0または1と書かれています.1と書いてある格子はすべて色紙で覆わなければなりません.色紙を貼るときは、紙の限界を超えたり、重ねたりしてはいけません.また、セルの境界と一致するようにします.0と書いた格子に色紙はありません.
用紙を与えた場合、1のマスをすべて貼るのに必要な最小色紙個数を求める.

入力


全部で10行あり、1ページあたりの数字です.

しゅつりょく


1をすべて上書きするために必要な最小色紙数を出力します.1をすべて上書きできない場合は、-1を出力します.

に近づく


近づくのは難しくない.すべての格子に色紙を貼ればいいです.
希望のない部分は後追跡で返し、Brook Forceで入手すればよい.
解法によっては、コードの長さが千差万別になる可能性があります.

に答える


最初はベクトルが関数パラメータだと思っていましたが、
そうする必要はないようだ.
残りをパラメータとして脱出ゲートに適用する.
y,x値の前処理も簡単でよい.
大きさ1~5を確認し、色紙があれば貼り付けます.
復帰する前に、値を変えて、出るときに値を変える仕事をすればいいです.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int answer = 30, paper[5] = { 5, 5, 5, 5, 5 };
vector<vector<int>> arr(10);

int use_paper()
{
	int ret = 25;
	FUP(i, 0, 4) ret -= paper[i];
	return ret;
}

void change(int y, int x, int len)
{
	FUP(i, y, y + len)
	{
		FUP(j, x, x + len)
		{
			arr[i][j] ^= 1;
		}
	}
}

void solve(int y, int x, int remain)
{
	if (remain == 0)
	{
		answer = min(answer, use_paper());
		return;
	}
	if (x >= 10)
	{
		solve(y + 1, 0, remain);
		return;
	}
	if (!arr[y][x]) solve(y, x + 1, remain);
	FUP(len, 0, 4)
	{
		if (x + len >= 10 || y + len >= 10) break;
		bool ok = true;
		FUP(i, y, y + len)
		{
			if (!arr[i][x + len]) ok = false;
		}
		FUP(j, x, x + len)
		{
			if (!arr[y + len][j]) ok = false;
		}
		if (!ok) break;
		if (!paper[len]) continue;
		change(y, x, len);
		paper[len]--;
		solve(y, x + len + 1, remain - (len + 1) * (len + 1));
		paper[len]++;
		change(y, x, len);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int remain = 0;
	FUP(i, 0, 9)
	{
		arr[i].resize(10);
		FUP(j, 0, 9)
		{
			CIN(arr[i][j]);
			remain += arr[i][j];
		}
	}
	solve(0, 0, remain);
	answer == 30 ? COUT(-1) : COUT(answer);

	return 0;
}
ソートの違い
▼▼TIL 12・CSS属性-position