[BOJ] 백준 1028번: 다이아몬드 광산

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

1028번: 다이아몬드 광산

R, C 가 750으로 (i, j) 좌표에서 우측 하단으로의 대각선 길이 DP[i][j][0], 좌측 하단으로의 대각선 길이 DP[i][j][1], 좌측 상단으로의 각선 길이 DP[i][j][2], 우측 상단으로의 대각선길이를 구해놓고 모든 좌표에 대하여 O(R*C*750*4)의 복잡도로 가능한 다이아몬드 크기를 구할 수 있습니다. (시간초과가 날것 같지만 가지치기를 통해 충분히 시간을 줄일 수 있습니다.)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
typedef long long ll;
int r, c;
int dp[777][777][4] = { 0, }; // 좌상 우상 좌하 우하
char buf[751][751];
inline bool recv(int x, int y,int len) {
	if (len < 2) {
		return true;
	}
	int nx = x + (len - 1);
	int ny = y + (len - 1);
	if (nx > r || ny > c || nx < 1 || ny < 1 || dp[nx][ny][1] < len) {
		return false;
	}

	int nx1 = nx + (len - 1);
	int ny1 = ny - (len - 1);
	if (nx1 > r || ny1 > c || nx1 < 1 || ny1 < 1 || dp[nx1][ny1][2] < len) {
		return false;
	}

	int nx2 = nx1 - (len - 1);
	int ny2 = ny1 - (len - 1);
	if (nx2 > r || ny2 > c || nx2 < 1 || ny2 < 1 || dp[nx2][ny2][3] < len) {
		return false;
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> buf[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	for (int i = r; i > 0; i--) {
		for (int j = c; j > 0; j--) {
			if (dp[i+1][j+1][0] == -1) {
				dp[i + 1][j + 1][0] = 0;
				int tx = i;
				int ty = j;
				while (tx && ty) {
					if (buf[tx][ty] == '1') {
						dp[tx][ty][0] = dp[tx + 1][ty + 1][0] + 1;
					}
					else {
						dp[tx][ty][0] = 0;
					}
					tx -= 1, ty -= 1;
				}
			}
		}
	}
	for (int i = r; i > 0; i--) {
		for (int j = 1; j <= c; j++) {
			if (dp[i + 1][j - 1][1] == -1) {
				dp[i + 1][j - 1][1] = 0;
				int tx = i;
				int ty = j;
				while (tx && ty<=c) {
					if (buf[tx][ty] == '1') {
						dp[tx][ty][1] = dp[tx + 1][ty - 1][1] + 1;
					}
					else {
						dp[tx][ty][1] = 0;
					}
					tx -= 1, ty += 1;
				}
			}
		}
	}
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (dp[i - 1][j - 1][2] == -1) {
				dp[i - 1][j - 1][2] = 0;
				int tx = i;
				int ty = j;
				while (tx <= r && ty<=c) {
					if (buf[tx][ty] == '1') {
						dp[tx][ty][2] = dp[tx - 1][ty - 1][2] + 1;
					}
					else {
						dp[tx][ty][2] = 0;
					}
					tx += 1, ty += 1;
				}
			}
		}
	}
	for (int i = 1; i <= r; i++) {
		for (int j = c; j > 0; j--) {
			if (dp[i - 1][j + 1][3] == -1) {
				dp[i - 1][j + 1][3] = 0;
				int tx = i;
				int ty = j;
				while (tx <= r && ty) {
					if (buf[tx][ty] == '1') {
						dp[tx][ty][3] = dp[tx - 1][ty + 1][3] + 1;
					}
					else {
						dp[tx][ty][3] = 0;
					}
					tx += 1, ty -= 1;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (ans > dp[i][j][0]) {
				continue;
			}
			for (int l = dp[i][j][0]; l > 0; l--) {
				if (recv(i, j, l)) {
					ans = max(ans, l);
					break;
				}
			}
		}
	}	
	cout << ans;
}