[Jungol] 정올 1013 Fivestar (Bitwise)

 Input 

5 6

.*....

.*****

.*....

*****.

.*....

 

 Output 

3 

출처: 정올 Jungol 1013 Fivestar

 

해당 포스팅은 Bitwise를 이용한 풀이

다른 방식 풀이: [Jungol] 1013 Fivestar

[Jungol] 정올 1013 Fivestar

 

---

#include <stdio.h>
int N, M, ans = 100;
int row[11], columnFive;
int calc(int r, int stat) {
       int i, j;
       if (row[r] == stat) return 0;
       for (i = 0; i <= M - 5; ++i) if ((stat | (31 << i)) == row[r])
              return 1;
       for (i = 0; i < M - 5; i++) {
              for (j = i + 1; j <= M - 5; ++j) {
                     int nstat = stat | (31 << i) | (31 << j);
                     if (nstat == row[r])
                           return 2;
              }
       }
       return 100;
}
int main() {
       scanf("%d %d", &N, &M);
       int i, j, bit = 1 << M;
       char c;
       columnFive = bit - 1; // 모든 열 위치에 소로로 놓을 수 있다고 가정
       for (i = 0; i < N; ++i) {
              for (j = 0; j < M; ++j) {
                     scanf(" %c", &c);
                     if (c == '.') // 세로로 놓을 수 없는 경우
                           columnFive &= ~(1 << j);
                     else // 하나의 행을 .* => 01 비트로 보아 10진 정수로
                           row[i] = row[i] + (1 << j);
              }
       }
       if (N < 5) columnFive = 0; // 5행이 되지 않으면 세로로 5개를 놓을 수 없다.
       for (i = 0; i < bit; i++) {
              if (~columnFive & i) continue;
              int vcnt = 0;
              for (j = 0; j < M; ++j) // 세로로 놓는 경우 세기
                     if ((i >> j) & 1) vcnt++;
              for (j = 0; j < N; ++j)
                     vcnt += calc(j, i);
              if (vcnt < ans) ans = vcnt;
       }
       printf("%d\n", ans == 100 ? -1 : ans);
}