import sys
input = sys.stdin.readline
def DFS(n,bit,cnt):
if DP[n][bit]:
return
if n == N-1:
DP[n][bit] = cnt
return
for bit1,cnt1 in bitlist[n+1]:
if bit&(bit1<<1) or (bit<<1)&bit1:
continue
DFS(n+1,bit1,cnt1)
if DP[n][bit] < DP[n+1][bit1]+cnt:
DP[n][bit] = DP[n+1][bit1]+cnt
T = int(input())
for _ in range(T):
N,M = map(int,input().split())
room = []
for i in range(N):
line = [*map(lambda x:1 if x=="x" else 0,[*input().strip()])]
room.append(int(("".join(map(str,line))),2))
bitlist = [[] for i in range(N)]
for n in range(N):
for bit in range(1<<M):
if bit&room[n] or bit&(bit<<1):
continue
cnt = bin(bit).count("1")
bitlist[n].append((bit,cnt))
DP = [[0]*(1<<M) for i in range(N)]
for bit,cnt in bitlist[0]:
DFS(0,bit,cnt)
print(max(DP[0]))
비트마스킹을 이용한 DP+DFS로 해결하는 문제이다.
외판원 순회 문제와 거의 비슷한 알고리즘으로 풀면 풀 수 있는 문제이다. 외판원 순회를 18번(...)이나 틀리면서 시행착오를 반복한 보람이 있는건지 꽤 쉽게 해결할 수 있었다.
알고리즘을 요약하면,
1. 일단 각 줄의 앉을 수 없는 자리와 앉을 수 있는 자리를 각각 1,0으로 취급하여 비트로 나타낸다.
2. 각 줄에서 앉을 수 없는 자리와 겹치지 않는 모든 bit 값을 구하고, 이때 1의 개수 (앉은 사람의 수)를 구하여 bitlist에 저장한다.
3. 비트마스킹을 이용한 DP+DFS로 역추적하여 최댓값을 구한다. 이때 현재 자리에서 1 shift한 값과 겹치지 않는 경우에 대해서 값을 갱신해준다. (앉을 수 없는 자리의 특성을 생각하자)
4. 최댓값을 구한다.
이 문제를 풀고 싶은 사람이 있다면 외판원 순회 문제를 먼저 풀고 이 문제를 푸는 것을 추천한다. 외판원 순회를 18번이나 틀린 보람을 느낄 수 있는 문제였다.
오늘의 교훈) 많이 틀리는것도 경험이라고 생각하자