The Java Program: I_mosaic/mosaicYiu.java

  1 /*
  2 ACM ICPC Southeast Regional Contest 2009
  3 
  4 Mosaic
  5 
  6 Author: Yiu Yu Ho
  7 */
  8 
  9 import java.io.*;
 10 import java.util.*;
 11 
 12 public class mosaicYiu
 13 {
 14         public Scanner in = new Scanner(System.in);
 15         public PrintStream out = System.out;
 16 
 17         public int Mod = 1000000;
 18 
 19         public int rn, cn, lim;
 20 
 21         public void main()
 22         {
 23                 int r, c, set;
 24                 int S;
 25 
 26                 cn = in.nextInt();
 27                 while(cn > 0)
 28                 {
 29                         rn = in.nextInt();
 30 
 31                         //We tile the rectangle in a row major order, as we proceed, we keep track of the interface between 
 32                         //the completely tiled area and the completely un-tiled area, which should consist of cn+1 cells.
 33                         //That is, if we are tiling cell (r, c), then cells before (r, c) in the row-major order must all be 
 34                         //tiled (occupied) and cells after (r+1, c) in the row-major order must be empty (unoccupied), the 
 35                         //status (tiled-ness) of cells in between (r, c) and (r+1, c), inclusive, are kept track by the bit mask. 
 36                         lim = 1 << (cn+1);
 37 
 38                         int[] cur, nxt;
 39                         
 40                         cur = new int[lim];
 41                         cur[0] = 1 % Mod;
 42 
 43                         for(r=0;r<rn;++r)
 44                         for(c=0;c<cn;++c)
 45                         {
 46                                 //cur retains information up to (r, c-1)
 47                                 //In the mask, the 0-th bit is (r, c), 1-st bit is (r, c+1), etc., and the cn-th bit is (r+1, c)
 48                                 nxt = new int[lim];
 49 
 50                                 for(set=0;set<lim;++set) if(cur[set] > 0)
 51                                 {
 52                                         if(in(0, set))
 53                                         {
 54                                                 //already filled, move to the next tile inheriting the current state
 55                                                 S = (set >> 1);
 56                                                 nxt[S] = (nxt[S] + cur[set]) % Mod;
 57                                         }
 58                                         else
 59                                         {
 60                                                 //not filled, try all 5 possible tilings
 61                                                 if(c+1 < cn && !in(1, set) && !in(cn, set))
 62                                                 {
 63                                                         S = (set >> 1);
 64                                                         S = on(0, S);
 65                                                         S = on(cn-1, S);
 66                                                         
 67                                                         //xx
 68                                                         //x.
 69                                                         nxt[S] = (nxt[S] + cur[set]) % Mod;
 70                                                         
 71                                                         S = on(cn, S);
 72 
 73                                                         //xx
 74                                                         //xx
 75                                                         nxt[S] = (nxt[S] + cur[set]) % Mod;
 76                                                 }
 77 
 78                                                 if(c+1 < cn && !in(cn, set))
 79                                                 {
 80                                                         S = (set >> 1);
 81                                                         S = on(cn-1, S);
 82                                                         S = on(cn, S);
 83                                                         
 84                                                         //x.
 85                                                         //xx
 86                                                         nxt[S] = (nxt[S] + cur[set]) % Mod;
 87                                                 }
 88 
 89                                                 if(c+1 < cn && !in(1, set))
 90                                                 {
 91                                                         S = (set >> 1);
 92                                                         S = on(0, S);
 93                                                         S = on(cn, S);
 94                                                         
 95                                                         //xx
 96                                                         //.x
 97                                                         nxt[S] = (nxt[S] + cur[set]) % Mod;
 98                                                 }
 99 
100                                                 if(c > 0 && !in(cn-1, set) && !in(cn, set))
101                                                 {
102                                                         S = (set >> 1);
103                                                         S = on(cn-2, S);
104                                                         S = on(cn-1, S);
105                                                         
106                                                         //.x
107                                                         //xx
108                                                         nxt[S] = (nxt[S] + cur[set]) % Mod;
109                                                 }
110                                         }
111                                 }//end for set = 0 .. lim-1
112 
113                                 cur = nxt;
114                         }//end for r = 0 .. rn-1, c = 0 .. cn-1
115                         
116                         //At the end, we want every before (rn+1, 0) to be tiled, and in the interface there are no tiles.
117                         out.println(cur[0]);
118                         cn = in.nextInt();
119                 }
120         }
121         
122         //Check if bit x is on (the corresponding cell is tiled)
123         public boolean in(int x, int set)
124         {
125                 return (set & (1<<x))!=0;
126         }
127         
128         //Turns on bit x from set and return the new set
129         public int on(int x, int set)
130         {
131                 return set | (1 << x);
132         }
133 
134         public static void main(String[] args)
135         {
136                 long startTime = System.currentTimeMillis();
137                 (new mosaicYiu()).main();
138                 long endTime = System.currentTimeMillis();
139 
140                 System.err.println("Time = " + (endTime - startTime) + "(ms)");
141         }
142 }
143