#include #include #include #define MAXDIM 4000 char map[MAXDIM][MAXDIM]; // Bludiště int R, S; // Rozměry bludiště int A, B; // Účinnost bomby (svislá a vodorovná) int Sx = -1, Sy = -1, Tx = -1, Ty = -1; // Souřadnice startu a cíle int px[MAXDIM+1][MAXDIM+1]; // 2D prefixové součty (pozor, indexy posunuty o 1!) uint16_t q[MAXDIM*MAXDIM][2]; // Fronta pro prohledávání // Prohledání mapy do šířky z políčka [xx,yy] a vyplnění chodeb znakem ch void bfs(int xx, int yy, int ch) { int r=0, w=0; // Čtecí a zapisovací index ve frontě // Pozor, vnořené funkce jsou rozšíření GCC, ve standardním Céčku nejsou void neigh(int i, int j) { if (i >= 0 && i < R && j >= 0 && j < S && map[i][j] != '#' && map[i][j] != ch) { map[i][j] = ch; q[w][0] = i, q[w][1] = j; w++; } } neigh(xx, yy); while (r < w) { int i = q[r][0], j = q[r][1]; r++; neigh(i-1, j); neigh(i+1, j); neigh(i, j-1); neigh(i, j+1); } } // Předvýpočet 2D prefixových součtů (1 započítáme za každé políčko dosažitelné z cíle) void calc_px(void) { for (int j=0; j<=S; j++) px[0][j] = 0; for (int i=1; i<=R; i++) { px[i][0] = 0; for (int j=1; j<=R; j++) px[i][j] = px[i-1][j] + px[i][j-1] - px[i-1][j-1] + (map[i-1][j-1] == 'T'); } } // Kolik políček dosažitelných z cíle je v zadaném obdélníku? int get_px(int x1, int y1, int x2, int y2) { return px[x2+1][y2+1] + px[x1][y1] - px[x2+1][y1] - px[x1][y2+1]; } // Pokud x neleží v intervalu , nahradíme ho příslušnou mezí intervalu int clamp(int x, int lo, int hi) { if (x < lo) return lo; if (x > hi) return hi; return x; } // Kolik políček dosažitelných z cíle leží v "obdélníku s ušima"? int get_win(int x1, int y1, int x2, int y2) { int x1r = clamp(x1, 0, R-1), x2r = clamp(x2, 0, R-1); int y1r = clamp(y1, 0, S-1), y2r = clamp(y2, 0, S-1); int s = get_px(x1r, y1r, x2r, y2r); if (x1 > 0) s += get_px(x1-1, y1r, x1-1, y2r); if (x2 < R-1) s += get_px(x2+1, y1r, x2+1, y2r); if (y1 > 0) s += get_px(x1r, y1-1, x2r, y1-1); if (y2 < S-1) s += get_px(x1r, y2+1, x2r, y2+1); return s; } int main(void) { // Načteme vstup scanf("%d%d%d%d", &R, &S, &A, &B); getchar(); // Sežereme konec řádku for (int i=0; i