首页 > 专题系列 > Java解POJ > POJ 2411 Mondriaan’s Dream [解题报告] Java
2013
11-11

POJ 2411 Mondriaan’s Dream [解题报告] Java

Mondriaan’s Dream

问题描述 :

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.



Expert as he was in this material, he saw at a glance that he’ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won’t turn into a nightmare!

输入:

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

输出:

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

样例输入:

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

样例输出:

1
0
1
2
3
5
144
51205

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{

 /* f[i][j]表示第i行,方格排布为二进制数j(第k位上为1表示凸出一个格子,为0表示不凸出)
   的方案数。用DFS进行状态转移。*/
 static  long  f[][]=new long[12][2048];
 static int  n, m;

 static void dfs(int i, int j, int jj, int s)//j是初始状态,jj是目标状态.s表示列数
{
    if (s == m)//把i行m列放好 
        f[i + 1][jj] += f[i][j];//等于I+1行被占去的格子的2进制为JJ应该可以多放f[i][j]的方略 
    else if ((jj & (1 << s)) == 0)//表示第J列能放1/0 
    {
        dfs(i, j, jj | (1 << s), s + 1);//放1 
        if (s < m - 1 && (jj & (1 << (s + 1))) == 0) dfs(i, j, jj, s + 2);//放0(横占2格) 
    }
    else//表示此处只能放0 
       dfs(i, j, jj & ~(1 << s), s + 1);//(jj & (1 << s)这个位置已经被占 
}
    
 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  while (sc.hasNext())
  {
      n=sc.nextInt();
      m=sc.nextInt();
      if(n+m==0) break;
      for(int i=0;i< f.length;i++)
        Arrays.fill(f[i],0);

      f[0][0] = 1;
      for (int i = 0; i < n; i++)
        for (int j = 0; j < (1 << m); j++)
          if (f[i][j]!=0) //剪枝(为0没有必要考虑) 
            dfs(i, j, j, 0);
      System.out.printf("%d\n", f[n][0]);//不占n行也即0~n-1放满的方法数 
   }
 }
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept