🔥14391번. 종이 조각_모든 열 비트마스킹

풀이 전략

1) 가로 인지, 세로인지 구별할 수 있게, 0과 1을 이용하자.
: 0인 경우에는 가로로 접근해야겠다.
1인 경우에는 세로로 접근해야 겠다. 를 생각해야 한다!

2) 각 행마다의 원소들 자리가 true인지 확인할 수 있는 조건을 만들어야 함.

그림 이해

가로

• 이런식으로 나열만 할 수 있따면, 비트마스킹으로 각 원소에 대한 처리가 가능
  
• 각 원소의 자릿수를 어떻게 만들 것이냐가 관건임.

세로

: 세로도 가로와 동일하게 만들어야 함.

코드

: 여기서 가로를 0이라고 가정을 한다면

1을 만났을 때 , 이미 구해진 49을 더하고, 이후에 나오는 74도 더해야 함.

생코드

#include <iostream>
#include <cstdio>
using namespace std;
int a[4][4];
int main() {
    int n, m;
    scanf("%d %d",&n,&m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%1d",&a[i][j]);
        }
    }
    int ans = 0;
    // 0: -, 1 : |
    for (int s=0; s<(1<<(n*m)); s++) {
        int sum = 0;
        for (int i=0; i<n; i++) {
            int cur = 0;
            for (int j=0; j<m; j++) {
                int k = i*m+j;
                if ((s&(1<<k)) == 0) {
                    cur = cur * 10 + a[i][j];
                } else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        for (int j=0; j<m; j++) {
            int cur = 0;
            for (int i=0; i<n; i++) {
                int k = i*m+j;
                if ((s&(1<<k)) != 0) {
                    cur = cur * 10 + a[i][j];
                } else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        ans = max(ans,sum);
    }
    cout << ans << '\n';
    return 0;
}