[白駿C+]14500テトロミノ

質問する

ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.
正方形は互いに重なり合ってはいけない.
図形はすべてつながっていなければなりません.
正方形の辺はつながっていなければならない.つまり、必ずしも頂点と重なる必要はありません.
4つの正方形を結ぶポリオミノをトロミノといい、以下の5種類があります.

美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.

入力

第1行目は、用紙の長手方向サイズNおよび横方向サイズMを与える.(4 ≤ N, M ≤ 500)
2行目からN行の紙に数字が書いてあります.i 1行目のj個の数字は、上からiの1番目のセル、左からjの1番目のセルに書かれた数字である.入力は1000を超えない自然数を与えます.

しゅつりょく

最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.
https://www.acmicpc.net/problem/14500

に答える

トロミノを対称に回転できるのでよく考えてみると
続く4コマはいずれもトロミノ.だから再帰構造を使います.
1つの座標x,yで4つの連続するセルを選択し、これらのセルの数字とを見ればよい.

重要な点はpush backとpop backの間に再帰的に呼び出される磁気関数を挿入すると
つまり、構造を作成して4つを選択し、ベクトルを再クリアして次の4つを選択できます.
しかし、このとき描かれたピンクのテトルミノは上記の方法では作れません.上のコードはWatden正方形に再アクセスしないからです.
ピンクのトロミノなら、ウォーデン正方形にアクセスするか、いっそ他のコードを追加する必要があります.

このコードは最大2つまで選択できます.
そして同時に2つを選択し、「凸」の形をしたテトロミノを生成します.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::pair;
typedef pair<int, int> pii;
int n, m, **map, max=0;

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
void init();
void func();
void pinkTetromino(int x, int y, vector<pii>& v, int cnt);
void tetromino(int X, int Y, vector<pii>& v, int cnt);

void init() {
	scanf("%d%d", &n, &m);
	map = new int* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[m];
		for (int j = 0; j < m; j++)
			scanf("%d", &map[i][j]);
	}
}

void func() {
	vector<pii> v;
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < m; y++) {
			v.push_back({ x, y });
			tetromino(x, y, v, 4);
			v.pop_back();

			v.push_back({ x, y });
			pinkTetromino(x, y, v, 4);
			v.pop_back();
		}
	}
	printf("%d", max);
}

void pinkTetromino(int x, int y, vector<pii> &v, int cnt) {
	if (cnt == 0) {
		int res = 0;
		for (int k = 0; k < 4; k++)
			res += map[v[k].first][v[k].second];

		if (max < res)
			max = res; //최댓값 갱신

		return;
	}
	if (cnt == 4) {
		for (int dir = 0; dir < 4; dir++) {
			int xx = x + dx[dir];
			int yy = y + dy[dir];
			bool exist = false;

			//올바른 인덱스인가
			if (xx < 0 || yy < 0 || xx == n || yy == m) continue;

			//이미 있는값인가
			for (int k = 0; k < v.size(); k++)
				if (v[k].first == xx && v[k].second == yy) exist = true;
			if (exist) continue;

			v.push_back({ xx, yy });
			pinkTetromino(xx, yy, v, cnt - 1); //재귀적호출
			v.pop_back();
		}
	}
	if (cnt == 3) {
		for (int dir1 = 0; dir1 < 4; dir1++) {
			for (int dir2 = dir1 + 1; dir2 < 4; dir2++) {
				int x1 = x + dx[dir1];
				int y1 = y + dy[dir1];
				int x2 = x + dx[dir2];
				int y2 = y + dy[dir2];
				bool exist = false;

				//올바른 인덱스인가
				if (x1 < 0 || y1 < 0 || x1 == n || y1 == m) continue;
				if (x2 < 0 || y2 < 0 || x2 == n || y2 == m) continue;

				//이미 있는값인가
				for (int k = 0; k < v.size(); k++) {
					if (v[k].first == x1 && v[k].second == y1) exist = true;
					if (v[k].first == x2 && v[k].second == y2) exist = true;
				}

				if (exist) continue;

				v.push_back({ x1, y1 });
				v.push_back({ x2, y2 });
				pinkTetromino(x1, y1, v, 0); //재귀적호출
				v.pop_back();
				v.pop_back();
			}
		}
	}


}

void tetromino(int x, int y, vector<pii> &v, int cnt) {
	if (cnt == 0) {
		int res = 0;
		for (int k = 0; k < 4; k++)
			res += map[v[k].first][v[k].second];

		if (max < res)
			max = res; //최댓값 갱신

		return;
	}
	for (int dir = 0; dir < 4; dir++) {
		int xx = x + dx[dir];
		int yy = y + dy[dir];
		bool exist = false;

		//올바른 인덱스인가
		if (xx < 0 || yy < 0 || xx == n || yy == m) continue;
		
		//이미 있는값인가
		for (int k = 0; k < v.size(); k++) 
			if (v[k].first == xx && v[k].second == yy) exist = true;
		if (exist) continue;

		v.push_back({ xx, yy });
		tetromino(xx, yy, v, cnt - 1); //재귀적호출
		v.pop_back();
	}

}

int main(void) {
	init();
	func();

	return 0;
}