fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. //게임판을 채울 수 있는 도형의 네 가지 모습
  8. int coverType[4][3][2] = {
  9.     {{0,0},{1,0},{0,1}},
  10.     {{0,0},{0,1},{1,1}},
  11.     {{0,0},{1,0},{1,1}},
  12.     {{0,0},{1,0},{1,-1}}
  13. };
  14.  
  15. //게임판의 x,y 위치에서
  16. //delta가 1이면 게임판을 type번 도형 모습으로 덮는다
  17. //delta가 -1이면 게임판의 type번 도형을 없앤다
  18. bool set(vector<vector<int>>& board, int y, int x, int type, int delta) {
  19.     bool ok = true;
  20.     for (int i = 0; i < 3; i++) {
  21.         //x,y를 기준으로 type번째 도형의 모습
  22.         int ny = y + coverType[type][i][0];
  23.         int nx = x + coverType[type][i][1];
  24.         //도형이 게임판 밖으로 나가거나 다른 도형과 겹치는지 확인
  25.         if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size())
  26.             ok = false;
  27.         //delta가 -1인 경우
  28.         else if ((board[ny][nx] += delta) > 1)
  29.             ok = false;
  30.     }
  31.     return ok;
  32. }
  33.  
  34. int cover(vector<vector<int>>& board) {
  35.     int y = -1;
  36.     int x = -1;
  37.     //도형의 맨 윗줄 왼쪽을 기준으로 가장 먼저 보이는 흰칸을 찾는다
  38.     for (int i = 0; i < board.size(); i++) {
  39.         for (int j = 0; j < board[i].size(); j++) {
  40.             if (board[i][j] == 0) {
  41.                 y = i;
  42.                 x = j;
  43.                 break;
  44.             }
  45.         }
  46.         if (y != -1) break;
  47.     }
  48.  
  49.     //모든 칸을 채운 경우
  50.     if (y == -1) return 1;
  51.     int ret = 0;
  52.     for (int type = 0; type < 4; ++type) {
  53.         //board(y,x)를 type번 도형으로 덮을 수 있으면 재귀 호출
  54.         if (set(board, y, x, type, 1))
  55.             ret += cover(board);
  56.         //덮었던 블록을 치운다
  57.         set(board, y, x, type, -1);
  58.     }
  59.     return ret;
  60. }
  61.  
  62. int main() 
  63. {
  64.     int C;
  65.     cin >> C;
  66.  
  67.     while (C--) 
  68.     {
  69.         int y, x;
  70.         cin >> y >> x;
  71.         vector<vector<int>> board(y, vector<int>(x, 0));
  72.         string input;
  73.  
  74.         for (int i = 0; i < y; i++) 
  75.         {
  76.             cin >> input;
  77.             for (int j = 0; j < input.length(); j++) 
  78.             {
  79.                 if (input[j] == '#')
  80.                     board[i][j] = 1;
  81.             }
  82.         }
  83.         cout << cover(board) << endl;
  84.     }
  85. }
Success #stdin #stdout 0.01s 5492KB
comments (?)
stdin
copy 
3 
3 7 
#.....# 
#.....# 
##...## 
3 7 
#.....# 
#.....# 
##..### 
8 10 
########## 
#........# 
#........# 
#........# 
#........# 
#........# 
#........# 
##########
stdout
copy 
0
2
1514
https://ideone.com/TPpZj7
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!