백준17860 Square Rooms

작성일 | In

문제 링크

  • http://icpc.me/17860

사용 알고리즘

  • 백트래킹

풀이

백트래킹으로 풀린다는 믿음을 갖고 풀면 됩니다.
어떤 영역을 정사각형으로 묶을 수 있는지 확인하는 건 Naive하게 해도 될 것 같긴 한데, 저는 혹시 몰라서 2D Prefix Sum을 사용했습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int n, m, a[111][111];
int coin[111][111], fuck[111][111];
int ans[111][111];

string SS = "#";

int chk(int i, int j, int ii, int jj){
    int C = coin[ii][jj] - coin[i-1][jj] - coin[ii][j-1] + coin[i-1][j-1];
    int F = fuck[ii][jj] - fuck[i-1][jj] - fuck[ii][j-1] + fuck[i-1][j-1];
    if(C == 1 && F == 0) return 0;
    if(C > 1 || F != 0) return 1;
    if(C == 0) return -1;
}

p nxt(){
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(!ans[i][j] && a[i][j] != -1) return p(i, j);
    return p(-1, -1);
}

bool f(int i, int j, int cnt){
    /*cout << "[[" << i << " " << j << "]]" << "\n";
    for(int x=1; x<=n; x++){
        for(int y=1; y<=m; y++){
            if(x == i && y == j) cout << "* ";
            else cout << ans[x][y] << " ";
        }
        cout << "\n";
    }*/
    int sum = 0;
    for(int k=0; i+k<=n && j+k<=m; k++){
        for(int x=i; x<=i+k; x++) sum += ans[x][j+k];
        for(int y=j; y<=j+k; y++) sum += ans[i+k][y];
        if(sum) break;
        int cc = chk(i, j, i+k, j+k);
        if(cc == -1) continue; if(cc == 1) break;
        for(int x=i; x<=i+k; x++) for(int y=j; y<=j+k; y++) ans[x][y] = cnt;
        p t = nxt();
        if(t.x == -1) return true;
        if(f(t.x, t.y, cnt+1)) return true;
        for(int x=i; x<=i+k; x++) for(int y=j; y<=j+k; y++) ans[x][y] = 0;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    freopen("../in", "r", stdin);
    freopen("../out", "w", stdout);
    freopen("../err", "w", stderr);
    #endif
    for(char i='A'; i<='Z'; i++) SS += i;
    for(char i='a'; i<='z'; i++) SS += i;
    cin >> n >> m;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        char c; cin >> c;
        if(c == '#') a[i][j] = -1, fuck[i][j] = 1;
        if(c == '$') a[i][j] = 1, coin[i][j] = 1;
    }
    for(int i=1; i<111; i++) for(int j=1; j<111; j++){
        coin[i][j] += coin[i-1][j]; fuck[i][j] += fuck[i-1][j];
        coin[i][j] += coin[i][j-1]; fuck[i][j] += fuck[i][j-1];
        coin[i][j] -= coin[i-1][j-1]; fuck[i][j] -= fuck[i-1][j-1];
    }
    p t = nxt();
    if(!f(t.x, t.y, 1)) cout << "elgnatcer";
    else{
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++) cout << SS[ans[i][j]];
            cout << "\n";
        }
    }
}