비트 필드를 이용한 다이나믹 프로그래밍

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 비트의 개수를 세는 보조 함수 (배치된 학생 수 계산에 사용)
static inline int countBits(int x) {
    return __builtin_popcount(x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int N, M;
        cin >> N >> M;
        vector<string> grid(N);
        for (int r = 0; r < N; r++) cin >> grid[r];

        // 각 행마다 앉을 수 있는 자리('.'인 칸)만 1로 표시한 마스크를 만든다
        // rowAvailMask[r]의 비트 c가 1이면 (r,c)에 학생을 배치할 수 있음
        vector<int> rowAvailMask(N, 0);
        for (int r = 0; r < N; r++) {
            int mask = 0;
            for (int c = 0; c < M; c++) {
                if (grid[r][c] == '.') mask |= (1 << c);
            }
            rowAvailMask[r] = mask;
        }

        // 각 행 r에 대해, 가능한 모든 배치 마스크를 미리 구해둔다.
        // 조건: (1) 해당 행에서 '.'인 자리의 부분집합이어야 함 (2) 같은 행에서 좌우 인접 금지
        // validMasks[r]: 행 r에서 가능한 마스크 목록
        // validCnt[r]: 해당 마스크에서 배치된 학생 수 (popcount)
        vector<vector<int>> validMasks(N);
        vector<vector<int>> validCnt(N);
        for (int r = 0; r < N; r++) {
            int avail = rowAvailMask[r];
            // 부분집합 열거 (avail의 모든 부분집합만 확인)
            int sub = avail;
            // 공집합(아무도 앉히지 않음)은 항상 유효하므로 먼저 추가
            validMasks[r].push_back(0);
            validCnt[r].push_back(0);
            while (sub) {
                // 좌우 인접 금지 검사: sub & (sub << 1) == 0이면 인접한 1이 없음
                if ((sub & (sub << 1)) == 0) {
                    validMasks[r].push_back(sub);
                    validCnt[r].push_back(countBits(sub));
                }
                // 다음 부분집합으로 이동
                sub = (sub - 1) & avail;
            }
        }

        // dpPrev[pm] = 이전 행까지 배치했을 때, 이전 행의 마스크가 pm일 때의 최대 인원수
        // dpCurr는 현재 행을 채울 때 임시로 사용
        const int NEG_INF = -1000000000;
        vector<int> dpPrev(1 << M, NEG_INF), dpCurr(1 << M, NEG_INF);

        // 첫 번째 행 초기화: 행 0에서 가능한 모든 배치를 적용
        for (size_t i = 0; i < validMasks[0].size(); i++) {
            int m0 = validMasks[0][i];
            dpPrev[m0] = max(dpPrev[m0], validCnt[0][i]);
        }

        // 이후 행들에 대해 전이 수행 (행 1부터 행 N-1까지)
        for (int r = 1; r < N; r++) {
            // 현재 행 dp 초기화
            fill(dpCurr.begin(), dpCurr.end(), NEG_INF);

            // 현재 행의 가능한 배치(cm)와 이전 행의 가능한 배치(pm)를 모두 시도
            for (size_t i = 0; i < validMasks[r].size(); i++) {
                int cm = validMasks[r][i];   // current mask
                int add = validCnt[r][i];    // 현재 행에서 배치되는 학생 수
                for (size_t j = 0; j < validMasks[r - 1].size(); j++) {
                    int pm = validMasks[r - 1][j]; // previous mask
                    int prevVal = dpPrev[pm];
                    if (prevVal == NEG_INF) continue;
                    // 대각선 충돌 금지:
                    // 이전 행의 열 c에 학생이 있으면, 현재 행의 열 c-1, c+1에 학생이 있으면 안됨
                    // 이를 비트로 검사: (cm & (pm << 1)) == 0, (cm & (pm >> 1)) == 0
                    if ((cm & (pm << 1)) != 0) continue; // 좌상향 대각선과 충돌
                    if ((cm & (pm >> 1)) != 0) continue; // 우상향 대각선과 충돌
                    dpCurr[cm] = max(dpCurr[cm], prevVal + add);
                }
            }
            // 다음 행을 위해 현재 값을 이전 값으로 스왑
            dpPrev.swap(dpCurr);
        }

        // 마지막 행에서 가능한 모든 마스크 중 최대값이 정답
        int answer = 0;
        for (int m = 0; m < (1 << M); m++) answer = max(answer, dpPrev[m]);
        cout << answer << '\n';
    }
    return 0;
}