Skip to content

Commit 0f5614e

Browse files
author
Haneul Kim
authored
Update 11967.cpp
1 parent d00ef4e commit 0f5614e

File tree

1 file changed

+58
-6
lines changed

1 file changed

+58
-6
lines changed

0x09/solutions/11967.cpp

Lines changed: 58 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,63 @@
1-
// Authored by : BaaaaaaaaaaarkingDog
2-
// Co-authored by : -
3-
// http://boj.kr/****************
1+
// Authored by : haneulkimdev
2+
// Co-authored by : BaaaaaaaaaaarkingDog
3+
// http://boj.kr/6f7aeed00c0f47b19cbb1a1aba45323b
44
#include <bits/stdc++.h>
55
using namespace std;
6+
#define X first
7+
#define Y second
68

7-
int main(void){
9+
int board[101][101];
10+
bool vis[101][101];
11+
vector<pair<int, int>> adj[101][101];
12+
int dx[4] = {1, 0, -1, 0};
13+
int dy[4] = {0, 1, 0, -1};
14+
int n, m;
15+
bool OOB(int a, int b) { return a < 1 || a > n || b < 1 || b > n; }
16+
17+
bool is_conn(pair<int, int> nxt) {
18+
for (int dir = 0; dir < 4; dir++) {
19+
int nx = nxt.X + dx[dir];
20+
int ny = nxt.Y + dy[dir];
21+
if (OOB(nx, ny)) continue;
22+
if (vis[nx][ny]) return 1;
23+
}
24+
return 0;
25+
}
26+
27+
int main(void) {
828
ios::sync_with_stdio(0);
929
cin.tie(0);
10-
11-
}
30+
cin >> n >> m;
31+
while (m--) {
32+
int x, y, a, b;
33+
cin >> x >> y >> a >> b;
34+
adj[x][y].push_back({a, b});
35+
}
36+
queue<pair<int, int>> Q;
37+
board[1][1] = 1;
38+
vis[1][1] = 1;
39+
Q.push({1, 1});
40+
while (!Q.empty()) {
41+
auto cur = Q.front();
42+
Q.pop();
43+
for (auto nxt : adj[cur.X][cur.Y]) {
44+
if (vis[nxt.X][nxt.Y]) continue;
45+
if (is_conn(nxt)) {
46+
vis[nxt.X][nxt.Y] = 1;
47+
Q.push({nxt.X, nxt.Y});
48+
}
49+
board[nxt.X][nxt.Y] = 1;
50+
}
51+
for (int dir = 0; dir < 4; dir++) {
52+
int nx = cur.X + dx[dir];
53+
int ny = cur.Y + dy[dir];
54+
if (OOB(nx, ny) || vis[nx][ny] || board[nx][ny] == 0) continue;
55+
vis[nx][ny] = 1;
56+
Q.push({nx, ny});
57+
}
58+
}
59+
int ans = 0;
60+
for (int i = 1; i <= n; i++)
61+
for (int j = 1; j <= n; j++) ans += board[i][j];
62+
cout << ans;
63+
}

0 commit comments

Comments
 (0)