Differences From Artifact [1708425009125a5d]:
- File
src/solver.d
- 2012-07-14 14:56:19 - part of checkin [c743b817b7] on branch trunk - death avoider for 'W'. (user: kinaba) [annotate]
To Artifact [4f413ed4f5088aec]:
- File
src/solver.d
- 2012-07-14 15:43:48 - part of checkin [901abf2f53] on branch trunk - optimized multiple lambda target. (user: kinaba) [annotate]
49 const Pos ro = g.map.robot; 49 const Pos ro = g.map.robot;
50 const Pos[] la = g.map.lambdas(); 50 const Pos[] la = g.map.lambdas();
51 const Pos li = g.map.lift; 51 const Pos li = g.map.lift;
52 52
53 Tuple!(char,int)[] cand; 53 Tuple!(char,int)[] cand;
54 char c = 'W'; 54 char c = 'W';
55 if( la.empty ) { 55 if( la.empty ) {
56 cand = search(g, ro, li, death); | 56 cand = search(g, ro, [li], death);
57 } else { 57 } else {
58 foreach(lam; la) <
59 cand ~= search(g, ro, lam, death); | 58 cand ~= search(g, ro, la, death);
60 } 59 }
61 cand ~= tuple('W',int.max); 60 cand ~= tuple('W',int.max);
62 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ 61 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
63 if(c1[1] != c2[1]) 62 if(c1[1] != c2[1])
64 return c1[1] < c2[1]; 63 return c1[1] < c2[1];
65 return c1[0] < c2[0]; 64 return c1[0] < c2[0];
66 })(cand); 65 })(cand);
................................................................................................................................................................................
95 if( cnt >= 3 && breath==1 ) { 94 if( cnt >= 3 && breath==1 ) {
96 forbidden_cell[ro.y][ro.x] = true; 95 forbidden_cell[ro.y][ro.x] = true;
97 } 96 }
98 97
99 return c; 98 return c;
100 } 99 }
101 100
102 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death) | 101 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos[] gs, string death
103 { 102 {
104 bool danger(int y, int x) 103 bool danger(int y, int x)
105 { 104 {
106 if(g.map[y+1,x] == '*') 105 if(g.map[y+1,x] == '*')
107 return true; 106 return true;
108 if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x 107 if(g.map[y+1,x-1]=='*' && (g.map[y,x-1]=='\\'||g.map[y,x
109 return true; 108 return true;
................................................................................................................................................................................
114 if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[ 113 if(g.map[y,x+1]=='*' && (g.map[y-1,x+1]=='*') && (g.map[
115 return true; 114 return true;
116 return false; 115 return false;
117 } 116 }
118 117
119 // avoid directly below '*' 118 // avoid directly below '*'
120 Tuple!(char,int)[] tryA() { 119 Tuple!(char,int)[] tryA() {
121 const(Pos)[] q = [o]; | 120 const(Pos)[] q;
> 121 foreach(p; gs)
> 122 if(!danger(p.y,p.x))
> 123 q ~= p;
122 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 124 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
123 if( !danger(o.y,o.x) ) { <
124 v[o.y][o.x]=true; | 125 foreach(p; q) v[p.y][p.x]=true;
125 for(int step=1; q.length; ++step) { | 126 for(int step=1; q.length; ++step) {
126 Pos[] q2; | 127 Pos[] q2;
127 foreach(p; q) { | 128 foreach(p; q) {
128 int[] dy=[-1,+1,0,0]; | 129 int[] dy=[-1,+1,0,0];
129 int[] dx=[0,0,-1,+1]; | 130 int[] dx=[0,0,-1,+1];
130 for(int i=0; i<4; ++i) { | 131 for(int i=0; i<4; ++i) {
131 int y = p.y+dy[i]; | 132 int y = p.y+dy[i];
132 int x = p.x+dx[i]; | 133 int x = p.x+dx[i];
133 if(v[y][x]) continue; | 134 if(v[y][x]) continue;
134 if(y==s.y && x==s.x) { | 135 if(y==s.y && x==s.x) {
135 char c = "UDRL"[ | 136 char c = "UDRL"[i];
136 if( death.count( | 137 if( death.count(c) == 0
137 return [ | 138 return [tuple(c,
138 } else if(forbidden_cell | 139 } else if(forbidden_cell[y][x]){
139 } else if(g.map[y,x]==' | 140 } else if(g.map[y,x]==' '||g.map
140 if(danger(y,x)) | 141 if(danger(y,x))
141 continue | 142 continue;
142 q2 ~= new Pos(y, | 143 q2 ~= new Pos(y,x);
143 v[y][x]=true; | 144 v[y][x]=true;
144 } <
145 } 145 }
146 } 146 }
147 q = q2; <
148 } 147 }
> 148 q = q2;
149 } 149 }
150 return []; 150 return [];
151 } 151 }
152 152
153 // any empty space is my ground 153 // any empty space is my ground
154 Tuple!(char,int)[] tryB() { 154 Tuple!(char,int)[] tryB() {
155 const(Pos)[] q = [o]; | 155 const(Pos)[] q;
> 156 foreach(p; gs) q ~= p;
156 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 157 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
157 v[o.y][o.x]=true; | 158 foreach(p; q) v[p.y][p.x]=true;
158 for(int step=10; q.length; ++step) { 159 for(int step=10; q.length; ++step) {
159 Pos[] q2; 160 Pos[] q2;
160 foreach(p; q) { 161 foreach(p; q) {
161 int[] dy=[-1,+1,0,0]; 162 int[] dy=[-1,+1,0,0];
162 int[] dx=[0,0,-1,+1]; 163 int[] dx=[0,0,-1,+1];
163 for(int i=0; i<4; ++i) { 164 for(int i=0; i<4; ++i) {
164 int y = p.y+dy[i]; 165 int y = p.y+dy[i];
................................................................................................................................................................................
178 q = q2; 179 q = q2;
179 } 180 }
180 return []; 181 return [];
181 } 182 }
182 183
183 // push rocks! 184 // push rocks!
184 Tuple!(char,int)[] tryC() { 185 Tuple!(char,int)[] tryC() {
185 const(Pos)[] q = [o]; | 186 const(Pos)[] q;
> 187 foreach(p; gs) q ~= p;
186 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 188 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
187 v[o.y][o.x]=true; | 189 foreach(p; q) v[p.y][p.x]=true;
188 for(int step=20; q.length; ++step) { 190 for(int step=20; q.length; ++step) {
189 Pos[] q2; 191 Pos[] q2;
190 foreach(p; q) { 192 foreach(p; q) {
191 int[] dy=[-1,+1,0,0]; 193 int[] dy=[-1,+1,0,0];
192 int[] dx=[0,0,-1,+1]; 194 int[] dx=[0,0,-1,+1];
193 for(int i=0; i<4; ++i) { 195 for(int i=0; i<4; ++i) {
194 int y = p.y+dy[i]; 196 int y = p.y+dy[i];