POJ 2222 - Deeper Blue

http://poj.org/problem?id=2222

概要

\(w \times h\) のチェス盤があり、この上に \(k\) 個の駒が乗っている。 ここからいくつか駒を取り除いて、どの駒も取れる駒が無いような状態にしたい。 このとき、最小でもいくつ取り除かなければならないかを答える。

制約

解法

全探索 + ちょっと枝刈り。

  1 #include <iostream>
  2 #include <vector>
  3 using namespace std;
  4 
  5 bool ok(char board[10][10], int H, int W)
  6 {
  7   for (int i = 0; i < H; i++) {
  8     for (int j = 0; j < W; j++) {
  9       switch (board[i][j]) {
 10         case 'K':
 11           for (int d = 0; d < 8; d++) {
 12             static const int di[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 13             const int k = i + di[d], l = j + dj[d];
 14             if (0 <= k && k < H && 0 <= l && l < W && board[k][l] != 'E') {
 15               return false;
 16             }
 17           }
 18           break;
 19         case 'Q':
 20           for (int d = 0; d < 8; d++) {
 21             static const int di[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
 22             int k = i + di[d], l = j + dj[d];
 23             while (0 <= k && k < H && 0 <= l && l < W) {
 24               if (board[k][l] != 'E') {
 25                 return false;
 26               }
 27               k += di[d];
 28               l += dj[d];
 29             }
 30           }
 31           break;
 32         case 'R':
 33           for (int d = 0; d < 4; d++) {
 34             static const int di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};
 35             int k = i + di[d], l = j + dj[d];
 36             while (0 <= k && k < H && 0 <= l && l < W) {
 37               if (board[k][l] != 'E') {
 38                 return false;
 39               }
 40               k += di[d];
 41               l += dj[d];
 42             }
 43           }
 44           break;
 45         case 'B':
 46           for (int d = 0; d < 4; d++) {
 47             static const int di[] = {-1, -1, 1, 1}, dj[] = {-1, 1, 1, -1};
 48             int k = i + di[d], l = j + dj[d];
 49             while (0 <= k && k < H && 0 <= l && l < W) {
 50               if (board[k][l] != 'E') {
 51                 return false;
 52               }
 53               k += di[d];
 54               l += dj[d];
 55             }
 56           }
 57           break;
 58         case 'N':
 59           for (int d = 0; d < 8; d++) {
 60             static const int di[] = {-1, -2, -2, -1, 1, 2, 2, 1}, dj[] = {-2, -1, 1, 2, 2, 1, -1, -2};
 61             const int k = i + di[d], l = j + dj[d];
 62             if (0 <= k && k < H && 0 <= l && l < W && board[k][l] != 'E') {
 63               return false;
 64             }
 65           }
 66           break;
 67       }
 68     }
 69   }
 70   return true;
 71 }
 72 
 73 int main()
 74 {
 75   for (string dummy; cin >> dummy;) {
 76     int W, H;
 77     cin >> W >> H;
 78     char board[10][10];
 79     vector<int> xs, ys;
 80     vector<char> cs;
 81     for (int i = 0; i < H; i++) {
 82       for (int j = 0; j < W; j++) {
 83         cin >> board[i][j];
 84         if (board[i][j] != 'E') {
 85           xs.push_back(i);
 86           ys.push_back(j);
 87           cs.push_back(board[i][j]);
 88         }
 89       }
 90     }
 91     cin >> dummy;
 92 
 93     const int N = xs.size();
 94     int ans = 20;
 95     for (unsigned s = 0; s < (1U<<N); s++) {
 96       const int n = __builtin_popcount(s);
 97       if (n >= ans) {
 98         continue;
 99       }
100       for (int i = 0; i < N; i++) {
101         if (s & (1U<<i)) {
102           board[xs[i]][ys[i]] = 'E';
103         }
104       }
105       if (ok(board, H, W)) {
106         ans = min(ans, n);
107       }
108       for (int i = 0; i < N; i++) {
109         board[xs[i]][ys[i]] = cs[i];
110       }
111     }
112     cout << "Minimum Number of Pieces to be removed: " << ans << endl;
113   }
114   return 0;
115 }
poj/2222.cc