BOJ_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を超えない自然数を与えます.

しゅつりょく

最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.

方法

ブルートフォース、この2つはヒントです.
ではすべての場合、1つずつ比較するだけで、出力の最高値を実現できます...!
特にアプローチはありません.
グラフィックシェイプに対応する配列のセルのみを必要とし、各要素の和をmaxval変数と比較します.

#include <cstdio>

int mymax(int a, int b){return a > b ? a : b;};
int main(void){
    int m,n,maxval = 0; scanf("%d %d",&m, &n);
	int tetro[m][n];
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			scanf("%d",&tetro[i][j]);
	for (int i = 0; i < m; i++){
		for (int j = 0; j <= n-4; j++){
			int hrz= 0, vrt=0;
			for (int h = j; h < j+4; h++) hrz += tetro[i][h];
			maxval = mymax(maxval,hrz);
		}
	}// 긴 녀석 가로이동
	for (int i = 0; i < n; i++){
		for (int j = 0; j <= m-4; j++){
			int vrt = 0;
			for (int h = j; h < j+4; h++) vrt += tetro[h][i];
			maxval = mymax(maxval,vrt);
		}
	}// 긴 녀석 세로이동

	for (int i = 0; i < m-1; i++){
		for (int j = 0; j <= n-2; j++){
			int sqr=0;
			for (int h = j; h < j+2; h++) sqr += (tetro[i][h]+tetro[i+1][h]);
			maxval = mymax(maxval,sqr);
		}
	}// 네모 녀석 이동
	
	for (int i = 0; i < m-1; i++){
		for (int j = 0; j <= n-3; j++){
			int tspin_up = 0,tspin_down = 0,times = 0,md,mu;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 2) md = tetro[i+1][h];
				tspin_down += tetro[i][h];
			}
			times = 0;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 2) mu = tetro[i][h];
				tspin_up += tetro[i+1][h];
			}
			maxval = mymax(maxval,mymax(tspin_down + md,tspin_up + mu));
		}
	}// 티스핀 가로 이동
	for (int i = 0; i < n-1; i++){
		for (int j = 0; j <= m-3; j++){
			int tspin_right = 0,tspin_left = 0,times = 0,mr,ml;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 2) mr = tetro[h][i+1];
				tspin_right += tetro[h][i];
			}
			times = 0;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 2) ml = tetro[h][i];
				tspin_left += tetro[h][i+1];
			}
			maxval = mymax(maxval,mymax(tspin_right + mr,tspin_left + ml));
		}
	}// 티스핀 세로 이동

	for (int i = 0; i < m-1; i++){
		for (int j = 0; j <= n-3; j++){
			int lspin1 = 0,lspin2=0, times = 0, dl, dr,ul,ur;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 1) dl = tetro[i+1][h];
				if(times == 3) dr = tetro[i+1][h];
				lspin1 += tetro[i][h];
			}
			maxval = mymax(maxval, mymax(lspin1+dl,lspin1+dr));
			times = 0;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 1) ul = tetro[i][h];
				if(times == 3) ur = tetro[i][h];
				lspin2 += tetro[i+1][h];
			}
			maxval = mymax(maxval, mymax(lspin2+ul,lspin2+ur));
		}
	}//엘스핀 3바닥 이동

	for (int i = 0; i < n-1; i++){
		for (int j = 0; j <= m-3; j++){
			int lspin1 = 0,lspin2=0, times = 0, ru, rd,lu,ld;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 1) ru = tetro[h][i+1];
				if(times == 3) rd = tetro[h][i+1];
				lspin1 += tetro[h][i];
			}
			maxval = mymax(maxval, mymax(lspin1+ru,lspin1+rd));
			times = 0;
			for (int h = j; h < j+3; h++){
				times++;
				if(times == 1) lu = tetro[h][i];
				if(times == 3) ld = tetro[h][i];
				lspin2 += tetro[h][i+1];
			}
			maxval = mymax(maxval, mymax(lspin2+lu,lspin2+ld));
		}
	}// 엘스핀 2바닥
	for (int i = 1; i < m-1; i++){
		for (int j = 0;j <= n-2;j++){
			int zspin1 = 0, times = 0, lu,rd,ru,ld;
			for (int h = j; h < j+2; h++){
				times++;
				if(times == 1) {
					lu = tetro[i-1][h];
					ld = tetro[i+1][h];
				}
				if(times == 2) {
					rd = tetro[i+1][h];
					ru = tetro[i-1][h];
				}
				zspin1 += tetro[i][h];
			}
			maxval = mymax(maxval,mymax(zspin1 + lu + rd,zspin1 + ld + ru));
		}
	}//z스핀 서있을때 이동
	for (int i = 1; i < n-1; i++){
		for (int j = 0;j <= m-2;j++){
			int zspin1 = 0, times = 0, lu,rd,ru,ld;
			for (int h = j; h < j+2; h++){
				times++;
				if(times == 1) {
					lu = tetro[h][i-1];
					ru = tetro[h][i+1];
				}
				if(times == 2) {
					ld = tetro[h][i-1];
					rd = tetro[h][i+1];
				}
				zspin1 += tetro[h][i];
			}
			maxval = mymax(maxval,mymax(zspin1 + lu + rd,zspin1 + ld + ru));
		}
	}//z스핀 누웠을 때 이동
	printf("%d",maxval);
	return 0;
}