fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. struct st {
  7.     int r, c, num;
  8. };
  9.  
  10. int n, m; //세로 가로
  11. int mp[8][8];
  12. int mp2[8][8] = {0};
  13. vector<st> v;
  14.  
  15. void up(int r, int c, int p = 1) {
  16.     for(int i = r; i >= 0; i--) {
  17.         if(mp[i][c] == 6)
  18.             break;
  19.         mp2[i][c] += p;
  20.     }
  21. }
  22.  
  23. void down(int r, int c, int p = 1) {
  24.     for(int i = r; i < n; i++) {
  25.         if(mp[i][c] == 6)
  26.             break;
  27.         mp2[i][c] += p;
  28.     }
  29. }
  30.  
  31. void right(int r, int c, int p = 1) {
  32.     for(int i = c; i < m; i++) {
  33.         if(mp[r][i] == 6)
  34.             break;
  35.         mp2[r][i] += p;
  36.     }
  37. }
  38.  
  39. void left(int r, int c, int p = 1) {
  40.     for(int i = c; i >= 0; i--) {
  41.         if(mp[r][i] == 6)
  42.             break;
  43.         mp2[r][i] += p;
  44.     }
  45. }
  46.  
  47. int check() {
  48.     int result = 0;
  49.     for(int i = 0; i < n; i++) {
  50.         for(int j = 0; j < m; j++) {
  51.             if(mp2[i][j] == 0)
  52.                 result++;
  53.         }
  54.     }
  55.     return result;
  56. }
  57.  
  58. int func(int i) {
  59.     cout << v.size() << endl;
  60.     if(i == v.size())
  61.         return check();
  62.  
  63.     int mn = 1e9;
  64.     switch(v[i].num) {
  65.     case 1:
  66.         up(v[i].r, v[i].c);
  67.         mn = min(mn, func(i+1));
  68.         up(v[i].r, v[i].c, -1);
  69.  
  70.         down(v[i].r, v[i].c);
  71.         mn = min(mn, func(i+1));
  72.         down(v[i].r, v[i].c, -1);
  73.  
  74.         left(v[i].r, v[i].c);
  75.         mn = min(mn, func(i+1));
  76.         left(v[i].r, v[i].c, -1);
  77.  
  78.         right(v[i].r, v[i].c);
  79.         mn = min(mn, func(i+1));
  80.         right(v[i].r, v[i].c, -1);
  81.  
  82.         break;
  83.     case 2:
  84.         up(v[i].r, v[i].c);
  85.         down(v[i].r, v[i].c);
  86.         mn = min(mn, func(i+1));
  87.         up(v[i].r, v[i].c, -1);
  88.         down(v[i].r, v[i].c, -1);       
  89.  
  90.         right(v[i].r, v[i].c);
  91.         left(v[i].r, v[i].c);
  92.         mn = min(mn, func(i+1));
  93.         left(v[i].r, v[i].c, -1);
  94.         right(v[i].r, v[i].c, -1);
  95.         break;
  96.     case 3:
  97.         up(v[i].r, v[i].c);
  98.         right(v[i].r, v[i].c);
  99.         mn = min(mn, func(i+1));
  100.         up(v[i].r, v[i].c, -1);
  101.         right(v[i].r, v[i].c, -1);
  102.  
  103.         up(v[i].r, v[i].c);
  104.         left(v[i].r, v[i].c);
  105.         mn = min(mn, func(i+1));
  106.         up(v[i].r, v[i].c, -1);
  107.         left(v[i].r, v[i].c, -1);
  108.  
  109.         down(v[i].r, v[i].c);
  110.         right(v[i].r, v[i].c);
  111.         mn = min(mn, func(i+1));
  112.         down(v[i].r, v[i].c, -1);
  113.         right(v[i].r, v[i].c, -1);
  114.  
  115.         down(v[i].r, v[i].c);
  116.         left(v[i].r, v[i].c);
  117.         mn = min(mn, func(i+1));
  118.         down(v[i].r, v[i].c, -1);
  119.         left(v[i].r, v[i].c, -1);
  120.  
  121.         break;
  122.     case 4:
  123.         right(v[i].r, v[i].c);
  124.         down(v[i].r, v[i].c);
  125.         left(v[i].r, v[i].c);
  126.         mn = min(mn, func(i+1));
  127.         right(v[i].r, v[i].c, -1);
  128.         down(v[i].r, v[i].c, -1);
  129.         left(v[i].r, v[i].c, -1);
  130.  
  131.         up(v[i].r, v[i].c);
  132.         down(v[i].r, v[i].c);
  133.         left(v[i].r, v[i].c);
  134.         mn = min(mn, func(i+1));
  135.         up(v[i].r, v[i].c, -1);
  136.         down(v[i].r, v[i].c, -1);
  137.         left(v[i].r, v[i].c, -1);
  138.  
  139.         up(v[i].r, v[i].c);
  140.         right(v[i].r, v[i].c);
  141.         left(v[i].r, v[i].c);
  142.         mn = min(mn, func(i+1));
  143.         up(v[i].r, v[i].c, -1);
  144.         right(v[i].r, v[i].c, -1);
  145.         left(v[i].r, v[i].c, -1);
  146.  
  147.         up(v[i].r, v[i].c);
  148.         right(v[i].r, v[i].c);
  149.         down(v[i].r, v[i].c);
  150.         mn = min(mn, func(i+1));
  151.         up(v[i].r, v[i].c, -1);
  152.         right(v[i].r, v[i].c, -1);
  153.         down(v[i].r, v[i].c, -1);
  154.  
  155.         break;
  156.     case 5:
  157.         up(v[i].r, v[i].c);
  158.         right(v[i].r, v[i].c);
  159.         down(v[i].r, v[i].c);
  160.         left(v[i].r, v[i].c);
  161.         mn = min(mn, func(i+1));
  162.         up(v[i].r, v[i].c, -1);
  163.         right(v[i].r, v[i].c, -1);
  164.         down(v[i].r, v[i].c, -1);
  165.         left(v[i].r, v[i].c, -1);
  166.         break; 
  167.     } 
  168.     return mn;
  169. }
  170.  
  171. int main() {
  172.     cin >> n >> m;
  173.     for(int i = 0; i < n; i++) {
  174.         for(int j = 0; j < m; j++) {
  175.             cin >> mp[i][j];
  176.  
  177.             if(mp[i][j] > 0) {
  178.                 mp2[i][j]++;
  179.                 v.push_back({i, j, mp[i][j]});
  180.             }
  181.         }
  182.     }
  183.     sort(v.begin(), v.end(), [](const st& l, const st& r) -> bool { return l.num > r.num; });
  184.  
  185.     cout << func(0);
  186.  
  187.     return 0;
  188. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0
stdout
copy 
2
1000000000
https://ideone.com/IFsfNJ
language:
C++14 (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!