[백준 14500] 테트로미노

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

#include <cstdio>
#include <cstring>
int N, M;
int A[500 + 2][500 + 2];
int ans;

int tetro_lookup[19][4][2] = {
	// |
	{{0, 0}, {0, 1}, {0, 2}, {0, 3}},
	// ㅡ
	{{0, 0}, {1, 0}, {2, 0}, {3, 0}},
	// cube
	{{0, 0}, {0, 1}, {1, 0}, {1, 1}},
	// |_
	{{0, 0}, {1, 0}, {2, 0}, {2, 1}},
	// _|
	{{0, 0}, {1, 0}, {2, 0}, {2, -1}},
	// -|
	{{0, 0}, {0, 1}, {1, 1}, {2, 1}},
	// |-
	{{0, 0}, {0, -1}, {1, -1}, {2, -1}},
	//'ㅡ
	{{0, 0}, {1, 0}, {1, 1}, {1, 2}},
	// ㅡ'
	{{0, 0}, {1, 0}, {1, -1}, {1, -2}},
	// ,ㅡ
	{{0, 0}, {-1, 0}, {-1, 1}, {-1, 2}},
	// ㅡ,
	{{0, 0}, {-1, 0}, {-1, -1}, {-1, -2}},
	// '-,
	{{0, 0}, {1, 0}, {1, 1}, {2, 1}}, 
	// ,-'
	{{0, 0}, {1, -1}, {1, 0}, {2, -1}},
	// _-
	{{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},
	// -_
	{{0, 0}, {0, 1}, {1, 1}, {1, 2}},
	//-,-
	{{0, 0}, {0, 1}, {0, 2}, {1, 1}},
	// _'_
	{{0, 0}, {0, 1}, {-1, 1}, {0, 2}}, 
	// |-
	{{0, 0}, {1, 0}, {1, 1}, {2, 0}},
	// -|
	{{0, 0}, {1, 0}, {2, 0}, {1, -1}}
};


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &A[i][j]);
		}
	}
}


int get_sum(int x, int y)
{
	int res = 0;
	for (int k = 0; k < 19; k++) {
		int each_sum = 0;
		bool done = true;
		for (int p = 0; p < 4; p++) {
			int nx = x + tetro_lookup[k][p][0];
			int ny = y + tetro_lookup[k][p][1];
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) {
				done = false;
				break;
			}
			each_sum += A[nx][ny];
		}
		if (done == true && each_sum > res) res = each_sum;
	}
	return res;
}


void find_max_value()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int res = get_sum(i, j);
			if (res > ans) ans = res;
		}
	}
}



int main()
{
	input();
	find_max_value();
	printf("%d\n", ans);
	return 0;
}

숙원사업들 하나씩 뿌셔가는 중.. ㅋㅋ

19개 도형에 대한 룩업테이블 잘 만들어주고, 입력받은 board 안 모든 좌표에 대하여 각 좌표를 기준으로 19가지 도형을 놓아보면서 가장 큰 수 가 만들어지는 경우 ans에 저장한다. 

이때 도형의 일부가 영역 밖으로 나가면 그것은 도형이 놓아졌다고 볼 수 없으므로, done이라는 플래그를 두어 해당 플래그가 true일 때만 최댓값을 갱신하도록 구현했다.