글 읽기 - bitmask 관련 코딩 질문...

h0ngjun7 9년 전 0

전 이 문제를 MCMF(Mincost Maxflow) 알고리즘으로 풀었는데 다른 분의 소스를 읽다보니 잘 이해가 안되서 질문드립니다.

kdk8747님의 소스인데...(혹시나 소스 공개가 문제가 된다면 곧바로 글을 지우겠습니다)

가로로 배열하는 부분은 이해가 되는데 세로로 배열하는 부분은 이해가 어렵습니다ㅠㅠ

s 변수를 쉬프트한 값에 ((1<<m)-1))를 & 연산해주면서 현재 속해있는 행에 대한 상태로 작업을 하는데

세로로 배열하는 경우에 한칸 쉬프트하고 1을 더해준 게, 다음 행의 해당 열에 이미 작업을 했다는 걸 어떻게 표시하는건지...음...

혹시 아시는 분은 설명해주시면 대단히 감사하겠습니다!

#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
int d[14*14][1<<14];
char a[22][22];
int b[6][6]={
    {10,8,7,5,0,1},
    { 8,6,4,3,0,1},
    { 7,4,3,2,0,1},
    { 5,3,2,2,0,1},
    { 0,0,0,0,0,0},
    { 1,1,1,1,0,0}
};
int n,m;
int f(int u, int s) {
    if(u >= n*m){
        if(u == n*m && s == 0)return 0;
        return -1234567890;
    }
    if (d[u][s] != -1) return d[u][s];
    int ans = f(u+1, (s<<1) & ((1<<m)-1));
    int x = u/m;
    int y = u%m;
 
    if(!(s & (1<<m-1))){
        if(!(s & (1<<m-2)) && y < m-1) //가로
            ans = max(ans, b[a[x][y]-'A'][a[x][y+1]-'A'] + f(u+2, (s<<2) & ((1<<m)-1)));
        if(x < n-1) //세로
            ans = max(ans, b[a[x][y]-'A'][a[x+1][y]-'A'] + f(u+1, ((s<<1)+1) & ((1<<m)-1)));
    }
    return d[u][s] = ans;
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i = 0; i < n; i ++) scanf("%s",a[i]);
    memset(d,-1,sizeof(d));
    printf("%d",f(0,0));
    return 0;
}