Advertisement
Guest User

Untitled

a guest
Apr 27th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.88 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define INF 987654321
  3. #define UP 0
  4. #define RIGHT 1
  5. #define DOWN 2
  6. #define LEFT 3
  7. using namespace std;
  8.  
  9. int Y, X, board[9][9];
  10. int dy[] = { -1,0,1,0 };
  11. int dx[] = { 0,1,0,-1 };
  12. int ans;
  13. vector<pair<int, int> > listCCTV;
  14.  
  15. void check(int y, int x, int dir,int idx) {
  16.     if (dir == UP) {
  17.         for (int i = y - 1; i >= 0 ; i--) {
  18.             if (board[i][x] == 6 )
  19.                 break;
  20.             else if ((1 <= board[i][x] && board[i][x] <= 5) || board[i][x] >= 7)
  21.                 continue;
  22.  
  23.             board[i][x] = idx+7;
  24.         }
  25.     }
  26.     else if (dir == RIGHT) {
  27.         for (int i = x + 1; i < X; i++) {
  28.             if (board[y][i] == 6 )
  29.                 break;
  30.             else if ((1 <= board[y][i] && board[y][i] <= 5) || board[y][i] >= 7)
  31.                 continue;
  32.            
  33.             board[y][i] = idx + 7;
  34.         }
  35.     }
  36.     else if (dir == DOWN) {
  37.         for (int i = y + 1; i < Y; i++) {
  38.             if (board[i][x] == 6 )
  39.                 break;
  40.             else if ((1 <= board[i][x] && board[i][x] <= 5) || board[i][x] >= 7)
  41.                 continue;
  42.  
  43.             board[i][x] = idx + 7;
  44.         }
  45.     }
  46.     else if (dir == LEFT) {
  47.         for (int i = x - 1; i >= 0; i--) {
  48.             if (board[y][i] == 6 )
  49.                 break;
  50.             else if ((1 <= board[y][i] && board[y][i] <= 5) || board[y][i] >= 7)
  51.                 continue;
  52.  
  53.             board[y][i] = idx + 7;
  54.         }
  55.     }
  56. }
  57. void uncheck(int y, int x, int dir, int idx) {
  58.     if (dir == UP) {
  59.         for (int i = y - 1; i >= 0; i--) {
  60.             if (board[i][x] == 6)
  61.                 break;
  62.             else if (1 <= board[i][x] && board[i][x] <= 5)
  63.                 continue;
  64.  
  65.             else if (board[i][x]==idx+7)
  66.                 board[i][x] = 0;
  67.         }
  68.     }
  69.     else if (dir == RIGHT) {
  70.         for (int i = x + 1; i < X; i++) {
  71.             if (board[y][i] == 6)
  72.                 break;
  73.             else if (1 <= board[y][i] && board[y][i] <= 5)
  74.                 continue;
  75.  
  76.             else if (board[y][i] == idx + 7)
  77.                 board[y][i] = 0;
  78.         }
  79.     }
  80.     else if (dir == DOWN) {
  81.         for (int i = y + 1; i < Y; i++) {
  82.             if (board[i][x] == 6)
  83.                 break;
  84.             else if (1 <= board[i][x] && board[i][x] <= 5)
  85.                 continue;
  86.             else if (board[i][x] == idx + 7)
  87.                 board[i][x] = 0;
  88.         }
  89.     }
  90.     else if (dir == LEFT) {
  91.         for (int i = x - 1; i >= 0; i--) {
  92.             if (board[y][i] == 6)
  93.                 break;
  94.             else if (1 <= board[y][i] && board[y][i] <= 5)
  95.                 continue;
  96.            
  97.             else if (board[y][i] == idx + 7)
  98.                 board[y][i] = 0;
  99.         }
  100.     }
  101. }
  102.  
  103. void solve(int idx) {
  104.     if (idx == listCCTV.size()) {
  105.         int ret = 0;
  106.         for (int i = 0; i < Y; i++) {
  107.             for (int j = 0; j < X; j++) {
  108.                 if (board[i][j] == 0) {
  109.                     ret++;
  110.                 }
  111.             }
  112.         }
  113.         if (ans > ret) {
  114.             ans = ret;
  115.         }
  116.         return;
  117.     }
  118.     int y = listCCTV[idx].first;
  119.     int x = listCCTV[idx].second;
  120.     int numCCTV = board[y][x];
  121.  
  122.     for (int dir = 0; dir < 4; dir++) {
  123.         if (numCCTV == 1) {
  124.             check(y, x, dir,idx);
  125.             solve(idx + 1);
  126.             uncheck(y, x, dir, idx);
  127.         }
  128.         else if (numCCTV == 2) {
  129.             check(y, x, dir, idx);
  130.             check(y, x, (dir + 2) % 4, idx);
  131.             solve(idx + 1);
  132.             uncheck(y, x, dir, idx);
  133.             uncheck(y, x, (dir + 2) % 4, idx);
  134.         }
  135.         else if (numCCTV == 3) {
  136.             check(y, x, dir, idx);
  137.             check(y, x, (dir + 1) % 4, idx);
  138.             solve(idx + 1);
  139.             uncheck(y, x, dir, idx);
  140.             uncheck(y, x, (dir + 1) % 4, idx);
  141.         }
  142.         else if (numCCTV == 4) {
  143.             check(y, x, dir, idx);
  144.             check(y, x, (dir + 1) % 4, idx);
  145.             check(y, x, (dir + 2) % 4, idx);
  146.             solve(idx + 1);
  147.             uncheck(y, x, dir, idx);
  148.             uncheck(y, x, (dir + 1) % 4, idx);
  149.             uncheck(y, x, (dir + 2) % 4, idx);
  150.         }
  151.         else if (numCCTV == 5) {
  152.             check(y, x, dir, idx);
  153.             check(y, x, (dir + 1) % 4, idx);
  154.             check(y, x, (dir + 2) % 4, idx);
  155.             check(y, x, (dir + 3) % 4, idx);
  156.             solve(idx + 1);
  157.             uncheck(y, x, dir, idx);
  158.             uncheck(y, x, (dir + 1) % 4, idx);
  159.             uncheck(y, x, (dir + 2) % 4, idx);
  160.             uncheck(y, x, (dir + 3) % 4, idx);
  161.         }
  162.     }
  163.  
  164. }
  165. int main() {
  166.     scanf("%d %d", &Y, &X);
  167.     ans = INF;
  168.     for (int i = 0; i < Y; i++) {
  169.         for (int j = 0; j < X; j++) {
  170.             scanf("%d", &board[i][j]);
  171.             if (board[i][j] != 6 && board[i][j] != 0)
  172.                 listCCTV.push_back(make_pair(i, j));
  173.         }
  174.     }
  175.     solve(0);
  176.     printf("%d\n",ans);
  177.     return 0;
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement