백준 1028 : 다이아몬드 광산

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

1028번: 다이아몬드 광산

설명
무지성 완탐+가지치기 했다가 시간초과가 났다. 잘보니 시간제한이 0.75초였다.
4개의 대각선 방향에 대해 최대로 뻗을 수 있는 길이를 dp로 저장하여 풀이하는 문제였다.

하나를 다이아몬드의 최상단으로 기준을 잡고 길이에 맞게 최하단의 좌표도 같이 설정한다.
두개의 좌표를 이용하여 각 좌표의 좌우 dp값을 비교해 다이아몬드를 만들 수 있다면 mx를 갱신한다.
길이 비교는 mx까지 하여 가지치기 한다. mx 아래는 볼 이유가 없기 때문

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[8] = { 1, -1, 0, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

int r, c;
string v[760];
int dp[800][800][4];

int func(int type, int x,int y) {
    if (x < 0 || y < 0 || x >= r || y >= c) return 0;
    if (v[x][y] == '0') return 0;

    int& ret = dp[x][y][type];
    if (ret != -1) return ret;

    int nx = x + dx[type + 4];
    int ny = y + dy[type + 4];
    dp[x][y][type] = func(type, nx, ny) + 1;

    return dp[x][y][type];
}

int main() {
    init();
    memset(dp, -1, sizeof(dp));
    int mx = 0;
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (v[i][j] == '1') {
                for (int type = 0; type < 4; type++) {
                    func(type, i, j);
                }
            }
        }
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (v[i][j] == '1') {
                int maxlen = min(dp[i][j][0], dp[i][j][1]);
                for (int len = maxlen; len > mx; len--) {
                    int ni = i + (len - 1) * 2;
                    if (ni >= r) continue;

                    if (dp[ni][j][3] >= len && dp[ni][j][2] >= len) {
                        mx = len; break;
                    }
                }
            }
        }
    }

    cout << mx << "\n";
}