SGU131--NYOJ435

참조 블로그
http://m.blog.csdn.net/blog/u012760629/36927465
http://www.cppblog.com/menrowitianya/archive/2014/06/23/207386.html
sgu131
제목: n*m의 직사각형을 하나 드릴게요. 1*2 또는 1각이 부족한 2*2 직사각형을 채워 드릴까요?
입력:
n,m(n,m<9)
출력:
T
사고방식:DP+DFS 해결, 코드는 대개 고정 모드이다. 먼저 줄부터 옮겨다니고 줄마다 단계이다. 줄마다 다음 줄마다 상태 이동 방정식 dp[i+1][status2]+=dp[i][status1]를 찾아낼 수 있다. 왜냐하면 다음 줄의 상태는 반드시 앞줄의 상태를 누적한 다음에 줄마다 상태를 분석하기 때문이다.모든 상황을 DFS로 반복해야 한다. 입력이 비교적 작기 때문에 현재 줄의 모든 열의 배치는 다음 줄의 배치에 영향을 줄 수 있기 때문에 u1, u2 두 변수를 설정하여 영향을 미칠지 여부를 판단할 수 있다.

#include<cstdio>
#include<cstring>
long long dp[11][1<<9];
int n,m,i;


void dfs(int row,int status1,int status2,int u1,int u2)
{
    if (row==m)
    {
        idp (u1==0 && u2==0) dp[i+1][status2]+=dp[i][status1];
        return;
    }
    if (u2==0)
    {
        if (u1==0)
        {
            dfs(row+1,status1<<1,(status2<<1)+1,0,0);
            dfs(row+1,status1<<1,(status2<<1)+1,1,0);
            dfs(row+1,status1<<1,(status2<<1)+1,0,1);
        }
        dfs(row+1,(status1<<1)+1-u1,(status2<<1)+1,0,1);
        dfs(row+1,(status1<<1)+1-u1,(status2<<1)+1,1,1);
    }
    if (u1==0) dfs(row+1,(status1<<1),(status2<<1)+u2,1,1);
    dfs(row+1,(status1<<1)+1-u1,(status2<<1)+u2,0,0);
}




int main()
{
    while(scandp("%d%d",&n,&m)!=EOF)
    {
        //m=n=0;
        memset(dp,0,sizeof(dp));
        if (n<m)
        {
            int t=n;
            n=m;
            m=t;
        }
        dp[0][(1<<m)-1]=1;
        for (i=0; i<n; i++) dfs(0,0,0,0,0);
        printdp("%I64d
",dp[n][(1<<m)-1]);
    }
    return 0;
}