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
4
4
#include < bits/stdc++.h>
5
5
using namespace std ;
6
+ #define X first
7
+ #define Y second
6
8
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 ) {
8
28
ios::sync_with_stdio (0 );
9
29
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