본문 바로가기
BOJ/C++

[BOJ] 17085. 십자가 2개 놓기

IamToday 2020. 4. 20. 21:21

 

* 십자가를 놓을 수 있는 최대 길이를 chk[][] 에 미리 저장을 해 놓는다. 

* 십자가는 한 좌표를 중심으로 상 하 좌 우 인접한 칸으로 퍼져나간다. 

* 이 특성을 이용해서 chk에는 몇 번이나 뻗어나갔는지를 저장한다. 

* dfs(int cnt, ll res) 에는 2개의 십자가를 놓았으면 최대값을 비교하여 갱신한다. (종료조건)

 

*(0,0) ~ (n,m)까지 검사하면서 chk[][]가 1이상일 때 (== map[][] 가 # 일때) 주변을 검사하면서 십자가가 겹쳐서 생성되지 않는지 검사한다. 

*무조건 한 십자가가 크다고 정답이 되는 것은 아니기 때문에 십자가의 크기가 chk[][] 의 값보다 작더라도 dfs()를 호출해서 다른 십자가도 놓을 수 있도록 한다. (line 81)

* visited는 십자가를 놓은 자리를 표시하는데, 완벽하게 네 방향에 십자가를 놓는 경우에만 표시할 수 있도록 한다.

 

 

?
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
//boj 십자가 2개 놓기 <a href="https://www.acmicpc.net/problem/17085">https://www.acmicpc.net/problem/17085</a>
 
int n, m;
char map[16][16];
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
 
bool visited[16][16];
int chk[16][16];
 
typedef long long ll;
ll ans = 0;
bool checkRange(int x, int y)
{
    if (x < 0 || x >= n || y < 0 || y >= m)
        return false;
    return true;
}
 
void dfs(int cnt, ll res)
{
    if (cnt == 2)
    {
        //최대 너비를 계산
        ans = ans > res ? ans : res;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (chk[i][j] && !visited[i][j])
            {
                bool c_visited[16][16];
                memcpy(c_visited, visited, sizeof(visited));
 
                int limit = chk[i][j] - 1;
                visited[i][j] = true;
                int sum = 1;
                if (!limit)
                {
                    dfs(cnt + 1, res * sum);
                    visited[i][j] = false;
                }
 
                int idx = 1;
                bool flag = true;
                while (limit-- && flag)
                {
                    for (int d = 0; d < 4; d++)
                    {
                        int nx = i + dx[d] * idx;
                        int ny = j + dy[d] * idx;
 
                        if (checkRange(nx, ny) && !visited[nx][ny])
                        {
                        }
                        else
                        {
                            flag = false;
                            break;
                        }
                    }
 
                    if (flag)
                    {
                        //4방향으로 모두 알맞게 십자가를 만들었다면
                        for (int d = 0; d < 4; d++)
                        {
                            int nx = i + dx[d] * idx;
                            int ny = j + dy[d] * idx;
                            visited[nx][ny] = true;
                            sum++;
                        }
 
                        dfs(cnt + 1, res * sum);
                        idx++;
                    }
                }
                memcpy(visited, c_visited, sizeof(visited));
            }
        }
    }
}
int main()
{
 
    ios_base::sync_with_stdio(0);
    <a href="http://cin.tie(0);">cin.tie(0);</a>
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == '#')
            {
                int idx = 1;
 
                bool flag = true;
                while (flag)
                {
                    for (int d = 0; d < 4; d++)
                    {
                        int nx = i + dx[d] * idx;
                        int ny = j + dy[d] * idx;
 
                        if (checkRange(nx, ny) && map[nx][ny] == '#')
                        {
                        }
                        else
                        {
                            flag = false;
                            break;
                        }
                    }
                    if (flag)
                    {
                        idx++;
                    }
                }
                chk[i][j] = idx;
            }
        }
    }
 
    dfs(0, 1);
    cout << ans << '\n';
    return 0;
}

 

 

TC
6 12
........#...
...#....#...
...#.#######
#######.#...
##.##...#...
...#........
ans = 81

7 7
...#...
...#...
...#...
#######
...####
...#.#.
...#...
ans = 25

'BOJ > C++' 카테고리의 다른 글

[BOJ] 4378. 트ㅏㅊ;  (0) 2020.04.25
[BOJ] 9019. DSLR  (0) 2020.04.25
[BOJ] 16939. 2X2X2 큐브  (0) 2020.04.20
[BOJ] 16932. 모양 만들기  (0) 2020.04.20
[BOJ] 17822. 원판 돌리기  (0) 2020.04.19

'BOJ/C++' Related Articles

티스토리툴바