main.cpp (7240B)
1 #include <vector> 2 #include <cstdio> 3 #include <algorithm> 4 #include <map> 5 #include <time.h> 6 7 using namespace std; 8 9 #define MAXR 77 10 #define MAXC 302 11 #define MAXL 2252 12 #define MAXA 10 13 #define MAXT 402 14 #define MAXB 55 15 16 char* output; 17 18 int R, C, A; 19 int L, V, B, T; 20 int rs, cs; 21 22 struct Pt{ 23 int r, c; 24 Pt(int r=0, int c=0) : r(r), c(c) {} 25 }; 26 27 vector<int> coverage[MAXR][MAXC]; // which targets are covered in r c 28 29 Pt dest[MAXA][MAXR][MAXC]; // where does the wind take us: -1 -1 = out 30 31 Pt target[MAXL]; 32 33 bool covered[MAXT][MAXL]; // does someone cover target l at time t 34 int left[MAXT][MAXR][MAXC]; // how many left to cover? 35 36 int solution[MAXT][MAXB]; 37 int oldsol[MAXT][MAXB]; 38 39 // for dynamic 40 int tab[MAXT][MAXA][MAXR][MAXC]; 41 int dir[MAXT][MAXA][MAXR][MAXC]; 42 43 int columndist(int c1, int c2) { 44 return min(abs(c1 - c2), C - abs(c1 - c2)); 45 } 46 47 int iscovered(int l, int r, int c) { 48 // does a loon at r c cover l? 49 int u = target[l].r, v = target[l].c; 50 return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V); 51 } 52 53 54 void calccoverage() { 55 // compute for each square which targets are covered 56 for (int r = 0; r < R; r++) 57 for (int c = 0; c < C; c++) 58 for (int l = 0; l < L; l++) 59 if (iscovered(l, r, c)) 60 coverage[r][c].push_back(l); 61 } 62 63 int decide_dyn(int b, int t, int a, int r, int c) { 64 return dir[t][a][r][c]; 65 } 66 67 int decide_sol(int b, int t, int a, int r, int c) { 68 return solution[t][b]; 69 } 70 71 int simulate(int b, int (*decide)(int, int, int, int, int)) { 72 // return totscore 73 // 74 // ok now follow the best 75 int totscore = 0; 76 int r = rs, c = cs, a = 0; 77 for (int t = 0; t < T; t++) { 78 //printf("loon %d at time %d is %d %d %d\n", b, t, a, r, c); 79 int bestda = (*decide)(b, t, a, r, c); 80 //printf("i choose %d\n", bestda); 81 // ok, apply bestda 82 a += bestda; 83 solution[t][b] = bestda; 84 Pt next = dest[a][r][c]; 85 r = next.r; 86 c = next.c; 87 if (r < 0) { 88 //printf("FAILLL\n"); 89 break; // loon is out 90 } 91 if (a > 0 && r >= 0) { 92 // update covered targets 93 //printf("coverage %d %d\n", r, c); 94 for (unsigned int i = 0; i < coverage[r][c].size(); i++) { 95 int l = coverage[r][c][i]; 96 totscore += covered[t+1][l] ? 0 : 1; 97 covered[t+1][l] = true; 98 } 99 } 100 } 101 return totscore; 102 } 103 104 105 int planify(int b) { 106 // planify one loon, b, based on the info of covered 107 // return totscore 108 int totscore = 0; 109 // compute left 110 for (int t = 0; t <= T; t++) 111 for (int r = 0; r < R; r++) 112 for (int c = 0; c < C; c++) { 113 int cscore = 0; 114 for (unsigned int i = 0; i < coverage[r][c].size(); i++) { 115 int l = coverage[r][c][i]; 116 cscore += covered[t][l] ? 0 : 1; 117 } 118 left[t][r][c] = cscore; 119 } 120 // planify loon b, t == T is sentinel 121 for (int t = 0; t <= T; t++) 122 for (int a = 0; a <= A; a++) 123 for (int r = 0; r < R; r++) 124 for (int c = 0; c < C; c++) 125 tab[t][a][r][c] = dir[t][a][r][c] = 0; 126 for (int t = T-1; t >= 0; t--) { 127 for (int a = 0; a <= A; a++) 128 for (int r = 0; r < R; r++) 129 for (int c = 0; c < C; c++) { 130 int bestda = 0, best = 0; 131 for (int da = -1; da <= 1; da++) { 132 if (a <= 1 && da < 0) 133 continue; 134 if (a + da > A) 135 continue; 136 Pt next = dest[a + da][r][c]; 137 if (next.r < 0) 138 break; 139 int rscore = ((a + da) > 0 ? left[t+1][next.r][next.c] : 0) + 140 tab[t+1][a+da][next.r][next.c]; 141 if (rscore > best || (rscore == best && (rand() % 2))) { 142 best = rscore; 143 bestda = da; 144 } 145 } 146 tab[t][a][r][c] = best; 147 dir[t][a][r][c] = bestda; 148 } 149 } 150 totscore += simulate(b, &decide_dyn); 151 return totscore; 152 } 153 154 void print_sol(int totscore) { 155 FILE *f = fopen(output, "w"); 156 157 // print solution 158 fprintf(f, "score %d\n", totscore); 159 160 for (int t = 0; t < T; t++) { 161 for (int b = 0; b < B; b++) 162 fprintf(f, "%d ", solution[t][b]); 163 fprintf(f, "\n"); 164 } 165 166 fclose(f); 167 } 168 169 int main(int argc, char **argv) { 170 int TOREPLAN = atoi(argv[1]); 171 srand(time(NULL)); 172 173 if (argc == 1) { 174 printf("syntax: ./a.out NREPLANIFY INPUT OUTPUT\n"); 175 return 1; 176 } 177 output = argv[3]; 178 179 180 scanf("%d%d%d", &R, &C, &A); 181 scanf("%d%d%d%d", &L, &V, &B, &T); 182 scanf("%d%d", &rs, &cs); 183 for (int l = 0; l < L; l++) { 184 int r, c; 185 scanf("%d%d", &r, &c); 186 target[l] = Pt(r, c); 187 } 188 for (int r = 0; r < R; r++) 189 for (int c = 0; c < C; c++) { 190 dest[0][r][c] = Pt(r, c); 191 } 192 for (int a = 1; a <= A; a++) 193 for (int r = 0; r < R; r++) 194 for (int c = 0; c < C; c++) { 195 int dr, dc; 196 scanf("%d%d", &dr, &dc); 197 int destr, destc; 198 destr = r + dr; 199 destc = (c + dc + C) % C; 200 if (destr < 0 || destr >= R) 201 destr = destc = -1; // out 202 dest[a][r][c] = Pt(destr, destc); 203 } 204 calccoverage(); 205 //for (int r = 0; r < R; r++) { 206 // for (int c = 0; c < C; c++) 207 // printf("%d ", (int) coverage[r][c].size()); 208 // printf("\n"); 209 //} 210 211 int totscore = 0; 212 213 if (argc > 3) { 214 // read existing file 215 216 FILE *fsol = fopen(argv[2], "r"); 217 for (int t = 0; t < T; t++) 218 for (int b = 0; b < B; b++) 219 fscanf(fsol, "%d", &(solution[t][b])); 220 fclose(fsol); 221 for (int b = 0; b < B; b++) 222 totscore += simulate(b, &decide_sol); 223 printf("existing sol has score %d\n", totscore); 224 } else { 225 for (int b = 0; b < B; b++) { 226 printf("%d\n", b); 227 totscore += planify(b); 228 } 229 printf("score %d\n", totscore); 230 print_sol(totscore); 231 } 232 233 int prevscore; 234 int counter = 0; 235 while(true) { 236 counter++; 237 counter = counter % B; 238 // keep old solution 239 for (int t = 0; t <= T; t++) 240 for (int b = 0; b <= B; b++) 241 oldsol[t][b] = solution[t][b]; 242 // choice of replanify 243 bool toreplan[MAXB]; 244 for (int b = 0; b < B; b++) 245 toreplan[b] = false; 246 //if (TOREPLAN == 1) { 247 // if one to replan, do it sequentially 248 // toreplan[counter] = true; 249 // } else { 250 for (int numb = 0; numb < TOREPLAN; numb++) 251 toreplan[rand() % B] = true; 252 // } 253 for (int t = 0; t <= T; t++) 254 for (int l = 0; l < L; l++) 255 covered[t][l] = false; 256 // now simulate 257 prevscore = totscore; 258 totscore = 0; 259 for (int b = 0; b < B; b++) { 260 if (toreplan[b]) 261 continue; 262 totscore += simulate(b, &decide_sol); 263 } 264 for (int b = 0; b < B; b++) { 265 if (!toreplan[b]) 266 continue; 267 printf("i replanify %d\n", b); 268 totscore += planify(b); 269 simulate(b, &decide_dyn); 270 } 271 272 if (totscore > prevscore) { 273 printf("score was %d is %d\n", prevscore, totscore); 274 print_sol(totscore); 275 } 276 if (totscore == prevscore) { 277 print_sol(totscore); 278 //printf("score was %d is still %d\n", prevscore, totscore); 279 } 280 281 if (totscore < prevscore) { 282 printf("score was %d is now %d, rollback!!\n", prevscore, totscore); 283 // rollback 284 for (int t = 0; t <= T; t++) 285 for (int b = 0; b <= B; b++) 286 solution[t][b] = oldsol[t][b]; 287 totscore = prevscore; 288 } 289 } 290 291 return 0; 292 } 293