01-10 14:41
Notice
Recent Posts
Recent Comments
Link
«   2025/01   »
일 월 화 수 목 금 토
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
Tags more
Archives
Today
Total
관리 메뉴

너와나의 관심사

백준 17232 본문

카테고리 없음

백준 17232

벤치마킹 2019. 8. 8. 21:46

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


이문제는 .. 이중 배열에서 시작점 (x1, y1) 에서 끝점 (x2, y2) 까지의 사각형 내에서의 합을 구하는 방식으로 풀수 있다. 

이경우 시간 복잡도는 O(NM) 으로 줄일수 있다. 

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <iostream>
#include <memory.h>
 
using namespace std;
 
int N, M, T;
int K, a, b;
 
char arr[305][105][105];
int acc[305][105][105];
 
 
void DBGPrint(int tt){
 
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){
            cout << arr[tt][i][j];
        }
        cout << "\n";
    }
 
 
    cout << endl;
}
 
 
void AnsPrint(int tt){
 
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= M; j++){
            cout << arr[tt][i][j];
        }
        cout << "\n";
    }
 
    //    cout << endl;
}
 
 
int main(void) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    //freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
 
    cin >> N >> M >> T;
    cin >> K >> a >> b;
 
    //memset(acc, '.', sizeof(acc));
    
    
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> arr[0][i][j];
 
    //DBGPrint(0);
 
    int tt = 0;
    while (tt <= T) {
 
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
 
                int k = 0;
                
                if ((arr[tt][i][j] == '*'))
                    k = 1;                 
 
                acc[tt][i][j] = acc[tt][i][j - 1] + acc[tt][i - 1][j] - acc[tt][i - 1][j - 1] + (arr[tt][i][j] == '*');
            }
        }
 
        int x1, y1, x2, y2;
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
 
 
                x1 = j - K;
                y1 = i - K;
 
                x2 = j + K;
                y2 = i + K;
 
                if (x1 < 1) x1 = 1;
                if (y1 < 1) y1 = 1;
 
                if (x2 > M) x2 = M;
                if (y2 > N) y2 = N; 
 
                int ans = acc[tt][y2][x2] - acc[tt][y1 - 1][x2] - acc[tt][y2][x1 - 1] + acc[tt][y1 - 1][x1 - 1];
                
                if (arr[tt][i][j] == '*')
                    ans--;
 
                if (arr[tt][i][j] == '*'){
 
                    if (a <= ans && ans <= b)
 
                        arr[tt + 1][i][j] = '*';
 
                    else if (ans < a || ans > b)
                        arr[tt + 1][i][j] = '.';
 
                }
                else {
                    if (a < ans && ans <= b)
                        arr[tt + 1][i][j] = '*';
                    else
                        arr[tt + 1][i][j] = '.';
                }            
            }
        }
 
        tt++;
    //    DBGPrint(tt);
 
    }
 
    AnsPrint(T);
    return 0;
}
 
cs


저작자표시
Comments