2105. 디저트 카페

BOJ 다이아몬드 광산이라는 문제가 생각나서 비슷하게 풀어봤다.

i,j에서 왼쪽 아래로 가는 대각선, 오른쪽 아래로 가는 대각선을 비트마스크로 저장해놓고 모든 위치에서 가능한 최대 길이의 마름모 꼴을 찾았다.

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
 
typedef long long ll;
 
int t, n;
int a[21][21];
ll d[21][21][2][21][2];
int dx[] = { 1,1 }, dy[] = { -1,1 };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        memset(d, -1, sizeof(d));
        cin >> n;
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) 
            cin >> a[i][j];
        for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
            for (int k = 0; k < 2; ++k) {
                ll bm1 = 0, bm2 = 0;
                for (int l = 0; l < n; ++l) {
                    int nx = i + dx[k] * l;
                    int ny = j + dy[k] * l;
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n) break;
                    if (a[nx][ny] > 50) {
                        // bm2
                        if (bm2&(1LL << (a[nx][ny] - 50))) break;
                        bm2 |= 1LL << (a[nx][ny] - 50);
                    }
                    else {
                        // bm1
                        if (bm1&(1LL << a[nx][ny])) break;
                        bm1 |= 1LL << a[nx][ny];
                    }
                    d[i][j][k][l][0] = bm1;
                    d[i][j][k][l][1] = bm2;
                }
            }
        }
        int ans = -1;
        for (int i = 0; i < n - 2; ++i) for (int j = 0; j < n - 1; ++j) {
            for (int k = min(j, n - i); k; --k) {
                int nx1 = i + dx[0] * k;
                int ny1 = j + dy[0] * k;
                if (nx1 < 0 || ny1 < 0 || nx1 >= n || ny1 >= n) continue;
                for (int l = min(n - 1 - j, n - 1 - i); l; --l) {
                    int nx2 = i + dx[1] * l;
                    int ny2 = j + dy[1] * l;
                    if (nx2 < 0 || ny2 < 0 || nx2 >= n || ny2 >= n) continue;
 
                    ll aa = d[i][j][0][k - 1][0];
                    ll bb = d[nx1][ny1][1][l - 1][0];
                    ll cc = d[i][j][1][l - 1][0] ^ (1LL << a[i][j]);
                    ll dd = d[nx2][ny2][0][k][0];
                    if (aa < 0 || bb < 0 || cc < 0 || dd < 0) continue;
                    if ((aa&(bb | cc | dd)) ||
                        (bb&(cc | dd)) ||
                        (cc&dd)) continue;
                    aa = d[i][j][0][k - 1][1];
                    bb = d[nx1][ny1][1][l - 1][1];
                    cc = d[i][j][1][l - 1][1];
                    if (a[i][j] > 50)
                        cc ^= (1LL << (a[i][j] - 50));
                    dd = d[nx2][ny2][0][k][1];
                    if (aa < 0 || bb < 0 || cc < 0 || dd < 0) continue;
                    if ((aa&(bb | cc | dd)) ||
                        (bb&(cc | dd)) ||
                        (cc&dd)) continue;
                    ans = max(ans, (k + l) * 2);
                }
            }
        }
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}