Advertisement
hwanil

Untitled

Jan 21st, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<queue>
  3. #include<memory.h>
  4. using namespace std;
  5.  
  6. char map[12][6];
  7. int check[12][6];
  8. int ans = 0;
  9. int dy[] = { -1,1,0,0 };
  10. int dx[] = { 0,0,-1,1 };
  11.  
  12. bool bfs(int y, int x) {
  13.     queue<pair<int, int> > q;
  14.     int cnt = 0;
  15.     check[y][x] = 1;
  16.     q.push({ y,x });
  17.  
  18.     //q가 빌때까지
  19.     while (!q.empty()) {
  20.         pair<int, int> now = q.front();
  21.         q.pop();
  22.  
  23.         //뿌요의 갯수 세기
  24.         cnt++;
  25.        
  26.         //인접해있는 같은 색의 뿌요가 있으면 큐에 넣어주자
  27.         for (int i = 0; i < 4; i++) {
  28.             int nY = now.first + dy[i];
  29.             int nX = now.second + dx[i];
  30.  
  31.             if (nY >= 0 && nY < 12 && nX >= 0 && nX < 6 && map[nY][nX] == map[now.first][now.second] && check[nY][nX] == 0) {
  32.                 check[nY][nX] = 1;
  33.                 q.push({ nY,nX });
  34.             }
  35.         }
  36.     }
  37.  
  38.     //인접해 있는 뿌요가 4개 이상이면 리턴 true
  39.     if (cnt >= 4)
  40.         return true;
  41.     else
  42.         return false;
  43. }
  44.  
  45. void restoreMap() {
  46.     queue<pair<int, int> > q;
  47.  
  48.     //11행부터 위로 올라가면서 뿌요가 있으면 큐에 넣어준다.
  49.     for (int i = 0; i < 6; i++) {
  50.         for (int j = 11; j >= 0; j--) {
  51.             if (map[j][i] != '.') {
  52.                 q.push({ j,i });
  53.             }
  54.         }
  55.     }
  56.  
  57.     //q가 빌때까지
  58.     while (!q.empty()) {
  59.         pair<int, int> now = q.front();
  60.         q.pop();
  61.        
  62.         //뿌요알파벳 저장
  63.         char alphabet = map[now.first][now.second];
  64.  
  65.         //아래로 한칸 내려 주기 위해
  66.         int nY = now.first + dy[1];
  67.        
  68.         //아래가 [0,12) && 빈공간이면
  69.         if (nY >= 0 && nY < 12 && map[nY][now.second] == '.') {
  70.            
  71.             //현재 뿌요 위치는 . 으로 바꿔주고
  72.             map[now.first][now.second] = '.';
  73.             //한 칸 내려준다
  74.             map[nY][now.second] = alphabet;
  75.             //그 밑에 칸에 또 있을 수 있으니 큐에 삽입
  76.             q.push({ nY, now.second });
  77.         }
  78.     }
  79.  
  80.     //뿌요를 재정립 끝
  81. }
  82. int main() {
  83.     //input
  84.     for (int i = 0; i < 12; i++)
  85.         for (int j = 0; j < 6; j++)
  86.             scanf(" %c", &map[i][j]);
  87.  
  88.     //아래부터 뿌요를 보자
  89.     for (int i = 11; i >= 0; i--) {
  90.  
  91.         bool flag = false;
  92.  
  93.         for (int j = 0; j < 6; j++) {
  94.             //check배열 초기화
  95.             memset(check, 0, sizeof(check));
  96.             flag = false;
  97.            
  98.             //뿌요가 있으면
  99.             if (map[i][j] != '.') {
  100.            
  101.                 //bfs(인접한 뿌요가 4개이상이면 flag= true, 4개 미만이면 flag=false;
  102.                 flag = bfs(i, j);
  103.                
  104.                 //인접해 있는게 4개 이상이면
  105.                 if (flag) {
  106.                
  107.                     //연쇄 하나 추가
  108.                     ans++;
  109.  
  110.                     //check된 곳이 뿌요가 있던 곳 이기 때문에 다 터트려 준다(.으로바꿔준다)
  111.                     for (int k = 11; k >= 0; k--) {
  112.                         for (int l = 0; l < 6; l++) {
  113.                             if (check[k][l] == 1) {
  114.                                 map[k][l] = '.';
  115.                             }
  116.                         }
  117.                     }
  118.  
  119.                     //터진 뿌요 위에 다른 색상의 뿌요가 있을 수 있으므로 아래로 내려준다.
  120.                     restoreMap();
  121.                 }
  122.                
  123.             }
  124.  
  125.         }
  126.     }
  127.     printf("%d\n", ans);
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement