The Java Program: I_mosaic/mosaicYiu.java
1
2
3
4
5
6
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
32
33
34
35
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
47
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
55 S = (set >> 1);
56 nxt[S] = (nxt[S] + cur[set]) % Mod;
57 }
58 else
59 {
60
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
68
69 nxt[S] = (nxt[S] + cur[set]) % Mod;
70
71 S = on(cn, S);
72
73
74
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
85
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
96
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
107
108 nxt[S] = (nxt[S] + cur[set]) % Mod;
109 }
110 }
111 }
112
113 cur = nxt;
114 }
115
116
117 out.println(cur[0]);
118 cn = in.nextInt();
119 }
120 }
121
122
123 public boolean in(int x, int set)
124 {
125 return (set & (1<<x))!=0;
126 }
127
128
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