1 import java.util.*; 2 import java.io.*; 3 import java.awt.*; 4 5 /** 6 * Solution to Mosaic 7 * 8 * The key to understanding this solution is to see a column of the mosaic 9 * as a bitmap - with the bit set (=1) if there's a tile there, and unset (=0) if not. 10 * Since there are at most 10 rows, that gives us 1023 possible bitmaps, which is 11 * manageable. 12 * 13 * We're going to try to build a Mosaic, column by column. Since the pieces are 2x2, 14 * we can't fill a column without leaving some residue in the next column. So, we're going 15 * to need to figure out, for any bitmap j representing a residue from the last column, 16 * how many ways can we fill this column and leave a residue of bitmap k in the next column? 17 * 18 * Here's an interesting thing - that number depends only on the number of rows. So, we can compute all 19 * of that a priori, before we ever start reading the data, rather than doing it over and over 20 * for each data set. 21 * 22 * Once we've got that figured out, then for each input, we need to fill the columns so 23 * that we start with a bitmap of 0 (on the edge, no residue), go through m columns, and 24 * end up with a bitmap of 0 (no residue - nothing hanging off the edge of the mosaic) 25 */ 26 public class mosaic 27 { 28 public Scanner sc; 29 public PrintStream ps; 30 31 public String toString() 32 { 33 return "mosaic"; 34 } 35 36 // step[i][k][k] is the number of ways, with i rows, of getting from bitmap j to bitmap k. 37 public int step[][][] = new int[11][][]; 38 39 // lists[i][j] holds the same info as step[i][j][k]. But, since the step[][][] array 40 // is sparse, it's more efficient to represent a row (step[i][j]) as a linked list, 41 // where k is omitted if step[i][j][k]==0. 42 public LinkedList<Point> lists[][] = new LinkedList[11][]; 43 44 // This is a global used by the fill() routine. 45 // It holds the base value of j before we start trying to fill the column. 46 public int base; 47 48 /** 49 * Figure out how many ways there are to fill a column, 50 * and the effect that has on the next column. Do it row by row. 51 * 52 * @param i Total number of rows 53 * @param j Bitmap so far on this column 54 * @param k Bitmap so far on the next column 55 * @param level Rows so far that we know are filled. 56 */ 57 public void fill( int i, int j, int k, int level ) 58 { 59 // We've filled the whole column 60 if( level>=i ) 61 { 62 // If we haven't gone over, record that 63 // we've found one more way of getting from base to k. 64 if( level==i && k<(1<<i) ) ++step[i][base][k]; 65 } 66 else 67 { 68 // Bits that are 1, 2, and 3 spots ahead 69 int b1 = 1<<level; 70 int b2 = b1<<1; 71 int b3 = b2<<1; 72 73 // Test those bits 74 boolean t1 = (j & b1) > 0; 75 boolean t2 = (j & b2) > 0; 76 boolean t3 = (j & b3) > 0; 77 78 if( !t1 && !t2 && !t3 ) 79 { 80 // Turn this: Into this: 81 // .. AA 82 // .. BA 83 // .. BB 84 fill( i, j|b3|b2|b1, k|b3|b1|b2, level+3 ); 85 86 // Turn this: Into this: 87 // .. AA 88 // .. AB 89 // .. BB 90 fill( i, j|b3|b2|b1, k|b3|b1|b2, level+3 ); 91 } 92 93 if( !t1 && !t2 ) 94 { 95 // We've got this: 96 // .. 97 // .. 98 99 // Try: 100 // XX 101 // XX 102 fill( i, j|b2|b1, k|b1|b2, level+2 ); 103 104 // Try: 105 // X. 106 // XX 107 fill( i, j|b1|b2, k|b1, level+2 ); 108 109 // Try: 110 // XX 111 // X. 112 fill( i, j|b1|b2, k|b2, level+2 ); 113 } 114 else if( t1 && !t2 ) 115 { 116 // We've got this: 117 // .. 118 // #. 119 120 // Try: 121 // XX 122 // #X 123 fill( i, j|b2, k|b1|b2, level+2 ); 124 125 // Try doing nothing 126 fill( i, j, k, level+1 ); 127 } 128 else if( !t1 && t2 ) 129 { 130 // We've got this: 131 // #. 132 // .. 133 134 // Try: 135 // #X 136 // XX 137 fill( i, j|b1, k|b1|b2, level+2 ); 138 } 139 else if( t1 && t2 ) 140 { 141 // All filled - move on 142 fill( i, j, k, level+1 ); 143 } 144 } 145 } 146 147 /** 148 * The main method. 149 * @throws Exception 150 */ 151 public void doit() throws Exception 152 { 153 sc = new Scanner( System.in ); // new Scanner( new File( "mosaic.judge" ) ); 154 ps = System.out; // new PrintStream( new FileOutputStream( "mosaic.solution" ) ); 155 156 // Compute steps[][][] and lists[][] a priori 157 for( int i=2; i<=10; i++ ) 158 { 159 // p = 2^i 160 int p = 1<<i; 161 162 // Create a pxp matrix 163 step[i] = new int[p][p]; 164 for( int j=0; j<p; j++ ) 165 { 166 Arrays.fill( step[i][j], 0 ); 167 } 168 169 // Also create an array of linked lists 170 lists[i] = new LinkedList[p]; 171 172 // Go through all possible bitmaps 173 for( int j=0; j<p; j++ ) 174 { 175 // fill() will modify its second parameter - so, 176 // we need to make the base bitmap available. 177 base = j; 178 179 // Fill the step[i][j][] row - figure out 180 // all the bitmaps you can get to from j when 181 // there are i rows. 182 fill( i, j, 0, 0 ); 183 184 // The matrix will be sparse - so, turn it into a linked list. 185 lists[i][j] = new LinkedList<Point>(); 186 for( int k=0; k<p; k++ ) if( step[i][j][k]>0 ) 187 { 188 // Represent as a point, where x = k, and y = # of ways 189 // of getting from j to k. 190 lists[i][j].add( new Point( k, step[i][j][k]) ); 191 } 192 } 193 } 194 195 for(;;) 196 { 197 // Read in n & m, exit if done 198 int n = sc.nextInt(); 199 int m = sc.nextInt(); 200 if( n==0 && m==0 ) break; 201 202 // p = 2^n, the number of possible bitmaps 203 int p = 1<<n; 204 205 // current[j] is the number of ways of achieving bitmap j 206 // on the current column 207 int current[] = new int[p]; 208 209 // next[k] is the number of ways of achieving bitmap k 210 // on the next column 211 int next[] = new int[p]; 212 213 // We'll start at the very beginning (a very good place to start) 214 // with one bitmap of 0, and no others. 215 Arrays.fill( next, 0 ); 216 next[0] = 1; 217 218 // Go through all of the columns 219 for( int i=0; i<m; i++ ) 220 { 221 // Swap current and next - last iterations' next[] 222 // is this iteration's current[] 223 int temp[] = current; 224 current = next; 225 next = temp; 226 227 // Start afresh 228 Arrays.fill( next, 0 ); 229 230 // Go through all possible bitmaps, and use the 231 // linked lists to see what bitmaps we can go to next 232 for( int j=0; j<p; j++ ) if( current[j]>0 ) for( Point q : lists[n][j] ) 233 { 234 // Remember how we build that point: q.x is k, and q.y is the number of ways 235 // to get from j to k. 236 // 237 // If there are current[j] ways of getting to bitmap j on the current column, 238 // and q.y ways of getting from there to bitmap q.x, then we've 239 // just found current[j]*q.y more ways of getting to bitmap q.x 240 // on the next column. So, add them in. 241 next[q.x] += current[j] * q.y; 242 243 // Mod to keep the numbers manageable. 244 next[q.x] %= 1000000; 245 } 246 } 247 248 // We're done! How many ways were there of achieving bitmap 0 249 // on the last iteration - that is, we nicely filled in the mosaic with 250 // nothing hanging over? 251 ps.println( next[0] ); 252 253 } 254 } 255 256 public static void main( String args[] ) throws Exception 257 { 258 long starttime = System.currentTimeMillis(); 259 new mosaic().doit(); 260 System.out.println( System.currentTimeMillis() - starttime ); 261 262 /* 263 Random random = new Random(); 264 for( int i=0; i<25; i++ ) 265 { 266 System.out.println( (random.nextInt(9)+2) + " " + (random.nextInt(501)+1)); 267 } 268 */ 269 } 270 }