トロミノ

アルゴリズム区分:実装,Brootforce

質問する

ポリオミの黄色の大きさは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を超えない自然数を与えます.
しゅつりょく
最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.
入力例1
5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1
サンプル出力1
19
入力例2
4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
サンプル出力2
20
入力例3
4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
サンプル出力3
7

問題を解く

ソースコード

#include <bits/stdc++.h>

using namespace std;

int n, m;
int graph[501][501];
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	for(int i = 1; i < n + 1; i++) {
		for(int j = 1; j < m + 1; j++) {
			cin >> graph[i][j];
		}
	}

	solve();
	
	return 0;
}

void solve() {
	int result = 0;
	int dx[][3] = {
		{0, 0, 0},
		{1, 2, 3},
		{0, 1, 1},
		{0, -1, -2},
		{1, 1, 1},
		{0, 1, 2},
		{-1, -1, -1},
		{0, -1, -2},
		{-1, -1, -1},
		{0, 1, 2},
		{1, 1, 1},
		{1, 1, 2},
		{0, -1, -1},
		{1, 1, 2},
		{0, 1, 1},
		{-1, -1, -1},
		{1, 0, -1},
		{1, 1, 1},
		{1, 0, -1}
	};
	int dy[][3] = {
		{1, 2, 3},
		{0, 0, 0},
		{1, 0, 1},
		{-1, -1, -1},
		{0, -1, -2},
		{1, 1, 1},
		{0, 1, 2},
		{1, 1, 1},
		{0, -1, -2},
		{-1, -1, -1},
		{0, 1, 2},
		{0, 1, 1},
		{1, 1, 2},
		{0, -1, -1},
		{1, 1, 2},
		{-1, 0 , 1},
		{-1, -1, -1},
		{-1, 0, 1},
		{1, 1, 1}
	};
	
	for(int i = 1; i < n + 1; i++) {
		for(int j = 1; j < m + 1; j++) {
			for(int k = 0; k < 19; k++) {
				int temp = graph[i][j];
				bool compare = true;
				
				for(int d = 0; d < 3; d++) {
					int nx = i + dx[k][d];
					int ny = j + dy[k][d];
					
					if(0 < nx && nx <= n && 0 < ny && ny <= m) {
						temp += graph[nx][ny];
					}
					else {
						compare = false;
						break;
					}
				}
				
				if(compare) {
					result = max(result, temp);
				}
			}
		}
	}
	
	cout << result << endl;
}

題出所:https://www.acmicpc.net/problem/145002

カイドウ草が白駿で「そうだ!!」判定を受けた