fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // 위 오 아래 왼
  5. int dx[4] = {1, 0, -1, 0}; // 행
  6. int dy[4] = {0, 1, 0, -1}; // 열
  7.  
  8. vector<pair<int, int>> swboard[103][103];
  9. void boj11967()
  10. {
  11. int N, M;
  12. int i, j;
  13. queue<pair<int, int>> Q;
  14. cin >> N >> M;
  15. int board[103][103]; // 0 꺼짐 1 불켜짐
  16. bool vis[103][103];
  17. bool connect = false;
  18.  
  19. // bfs 두번 돌림
  20. // 첫번째에서 불켜진 보드 그리고
  21. // 두번째에서 배시 움식여서 방 갯수 카운트
  22. for(i=0; i<N; i++)
  23. {
  24. fill(board[i], board[i]+N, 0);
  25. fill(vis[i], vis[i]+N, 0);
  26. }
  27.  
  28. for(i=0; i<M; i++)
  29. {
  30. int x, y, a, b;
  31. cin >> x >> y >> a >> b;
  32. swboard[x-1][y-1].push_back({a-1, b-1});
  33. }
  34.  
  35. board[0][0] = 1;
  36. vis[0][0] = 1;
  37. Q.push({0, 0});
  38.  
  39. while (!Q.empty())
  40. {
  41. auto cur = Q.front(); Q.pop();
  42.  
  43. for(auto x : swboard[cur.first][cur.second]) {
  44. connect = false;
  45. if(vis[x.first][x.second]) continue;
  46. for(int dir=0; dir<4; dir++)
  47. {
  48. int nx = x.first + dx[dir];
  49. int ny = x.second + dy[dir];
  50. if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
  51. if(vis[nx][ny]) connect = true;
  52. }
  53. if(connect) {
  54. vis[x.first][x.second] = 1;
  55. Q.push({x.first, x.second});
  56. }
  57. board[x.first][x.second] = 1;
  58.  
  59. }
  60. for(int dir=0; dir<4; dir++)
  61. {
  62. int nx = cur.first + dx[dir];
  63. int ny = cur.second + dy[dir];
  64. if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
  65. if(vis[nx][ny] || board[nx][ny] == 0) continue;
  66. Q.push({nx, ny});
  67. vis[nx][ny] = 1;
  68. }
  69. }
  70.  
  71.  
  72. int ans = 0;
  73. for(i=0; i<N; i++)
  74. for(j=0; j<N; j++)
  75. if(board[i][j] == 1)
  76. ans++;
  77.  
  78. cout << ans;
  79.  
  80. }
  81.  
  82. int main()
  83. {
  84. ios::sync_with_stdio(0);
  85. cin.tie(0);
  86.  
  87. boj11967();
  88. }
Success #stdin #stdout 0.01s 5436KB
stdin
2 1
1 1 2 2
stdout
2