N coding

3654_L퍼즐 본문

PS

3654_L퍼즐

NYWOO19 2018. 8. 29. 15:55




타워 디펜스를 풀고나서 이 문제를 풀면 비슷하게 보인다.
black인 노드를 기준으로 세로방향(위 t, 아래 f) 가로방향 (왼 t, 아래 f)의 두가지 상태를 가진다.
black인 노드의 사방을 보면서 만약 위나 아래중에 하나만 존재한다면 얘는 반드시 그 하나랑 연결되야 하므로
논리식을 세워준다. (black i의 위 or black i의 위)
역시 가로방향도 마찬가지로 해준다.

만약 black i가 위에 잇는 w랑 연결이 된다면 
그 w랑 연결될 수 잇는 가능성이 있는 다른 아이들은 다 연결불가이다.
그런 의미에서 w를 타고 들어가서 (black i의 아래 or black j의 ~방향)의 논리식을 세워줬다.




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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
using namespace std;
 
int t, N, M, num, SN, base, cnt;
char maap[505][505];
vector<pair<int, int>> Black;
vector<int> sn, fin, dfsn;
vector<vector<int>> adj;
int m[505][505];
stack<int> st;
 
int a[8] = { -1, 0, 1, 0, //위, 왼, 아래, 오
0, -1, 0, 1 };
 
int nott(int x) {
    return (x > base ? x - base : x + base);
}
 
int avail(int x, int y, char c = 'W') {
    return (x >= 0 && y >= 0 && x < N && y < M && maap[x][y] == c);
}
 
void conn(int x, int y, int b, int bb) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + a[i];
        int ny = y + a[i + 4];
 
        if (avail(nx, ny, 'B')) {
            if (m[nx][ny] == bb) continue;
            //w가 b의 i방향이라면
            //w를 b의 (i+2)%4방향으로 연결했을때, 다른 애들은 (j+2)%4방향으로 연결불가
            int mb = (i % 2 ? m[nx][ny] + base / 2 : m[nx][ny]);
            if (i <= 1) mb = nott(mb);
            adj[b].push_back(nott(mb));
            adj[mb].push_back(nott(b));
        }
    }
}
 
int dfs(int cur) {
    dfsn[cur] = ++num;
    st.push(cur);
 
    int ret = dfsn[cur];
    for (auto next : adj[cur]) {
        if (dfsn[next] == 0) ret = min(ret, dfs(next));
        else if (fin[next] == 0) ret = min(ret, dfsn[next]);
    }
 
    if (ret == dfsn[cur]) {
        SN++;
        while (1) {
            int curr = st.top(); st.pop();
            fin[curr] = 1;
            sn[curr] = SN;
            if (curr == cur) break;
        }
    }
    return ret;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> t;
    while (t--) {
        Black.clear(); sn.clear(); fin.clear();
        dfsn.clear(); adj.clear();
        memset(m, 0, sizeof(m));
        num = SN = 0;
        int W = 0;
        cin >> N >> M;
        for (int i = 0; i < N; ++i) {
            cin >> maap[i];
            for (int j = 0; j < M; ++j) {
                if (maap[i][j] == 'B') {
                    Black.push_back({ i, j });
                    m[i][j] = Black.size();
                }
                else if (maap[i][j] == 'W') {
                    W++;
                }
            }
        }
 
        base = Black.size() * 2;
        sn.resize(base * 2 + 1), fin.resize(base * 2 + 1);
        dfsn.resize(base * 2 + 1), adj.resize(base * 2 + 1);
        //각각의 black은 위 t, 아래 f/ 왼t, 오f
        // 위 or ~위(아래) // 왼 or ~왼(오른)
        cnt = 0;
        int ok = 1;
 
        if (W  != base) {
            cout << "NO\n"; continue;
        }
 
        for (auto& b : Black) { 
            cnt++;
            int t = avail(b.first - 1, b.second);
            int f = avail(b.first + 1, b.second);
            if (t && !f) adj[nott(cnt)].push_back(cnt);
            else if (!t && f) adj[cnt].push_back(nott(cnt));
            else if (!f && !t) {
                ok = 0; break;
            }
 
            if (t) {
                conn(b.first - 1, b.second, cnt, cnt);
            }
            if (f) {
                conn(b.first + 1, b.second, nott(cnt), cnt);
            }
 
            t = avail(b.first, b.second - 1);
            f = avail(b.first, b.second + 1);
            if (t && !f) adj[nott(cnt + base / 2)].push_back(cnt + base / 2);
            else if (!t && f) adj[cnt + base / 2].push_back(nott(cnt + base / 2));
            else if (!f && !t) {
                ok = 0; break;
            }
        
            if (t) {
                conn(b.first, b.second - 1, cnt + base / 2, cnt);
            }
            if (f) {
                conn(b.first, b.second + 1, nott(cnt + base / 2), cnt);
            }
        }
 
        if (ok == 0) { //만약 선택핤 수 있는 블록의 형태가 안만들어진다면 바로 no
            cout << "NO\n"; continue;
        }
 
 
        for (int i = 1; i <= base * 2; ++i) {
            if (dfsn[i] == 0) dfs(i);
        }
 
        for (int i = 1; i <= base; ++i) {
            if (sn[i] == sn[nott(i)]) {
                ok = 0; break;
            }
        }
 
        if (ok) cout << "YES\n";
        else cout << "NO\n";
    }
 
}
cs


'PS' 카테고리의 다른 글

13576_Prefix와 Suffix  (0) 2018.08.31
2809_아스키거리  (3) 2018.08.30
4217_신성문자  (0) 2018.08.30
15940_네트워크 연결  (2) 2018.08.29
3789_Hidden password  (0) 2018.08.29
'PS' Related Articles more