/* * No.3504 Insert Maze * * Key idea: We can insert any number of all-'.' rows/columns. * Model this as a Dijkstra on an extended graph with 4 node types: * Type 0: Grid cell (i,j) — H*W nodes * Type 1: Row-corridor (r,j) — (H-1)*W nodes [between row r and r+1, at column j] * Type 2: Col-corridor (i,c) — H*(W-1) nodes [between col c and c+1, at row i] * Type 3: Intersection (r,c) — (H-1)*(W-1) nodes [row-corridor r meets col-corridor c] * * Edges (cost 1 each): * Grid(i,j) <-> Grid neighbor (if passable) * Grid(i,j) <-> RowCorridor(i-1,j) [enter corridor above] * Grid(i,j) <-> RowCorridor(i,j) [enter corridor below] * Grid(i,j) <-> ColCorridor(i,j-1) [enter corridor left] * Grid(i,j) <-> ColCorridor(i,j) [enter corridor right] * RowCorridor(r,j) <-> RowCorridor(r,j±1) * RowCorridor(r,j) <-> Intersection(r,j-1) [enter col-corridor left] * RowCorridor(r,j) <-> Intersection(r,j) [enter col-corridor right] * ColCorridor(i,c) <-> ColCorridor(i±1,c) * ColCorridor(i,c) <-> Intersection(i-1,c) [enter row-corridor above] * ColCorridor(i,c) <-> Intersection(i,c) [enter row-corridor below] * Intersection(r,c) <-> Intersection(r,c±1) [move along row-corridor] * Intersection(r,c) <-> Intersection(r±1,c) [move along col-corridor] * * Total nodes ~ 4*H*W <= 16*10^6 with H,W<=2000. * Using Dijkstra with binary heap (all edge weights = 1, so BFS works too). */ #include #include #include #define MAXH 2001 #define MAXW 2001 static int H, W; static char grid[MAXH][MAXW]; /* Node encoding */ /* We use int node IDs */ /* Type 0: Grid(i,j) id = i*W + j range [0, H*W) */ /* Type 1: RowCor(r,j) id = H*W + r*W + j range [H*W, H*W+(H-1)*W) */ /* Type 2: ColCor(i,c) id = H*W+(H-1)*W + i*(W-1) + c range [..., ...+H*(W-1)) */ /* Type 3: Inter(r,c) id = above + H*(W-1) + r*(W-1) + c range [...] */ static int base1, base2, base3, total_nodes; static inline int grid_id(int i, int j) { return i*W + j; } static inline int rowcor_id(int r, int j) { return base1 + r*W + j; } static inline int colcor_id(int i, int c) { return base2 + i*(W-1) + c; } static inline int inter_id(int r, int c) { return base3 + r*(W-1) + c; } /* BFS queue (all edges weight 1) */ static int *dist; static int *queue; static inline int passable(int i, int j) { return grid[i][j] != '#'; } int main(void) { scanf("%d %d", &H, &W); for (int i = 0; i < H; i++) scanf("%s", grid[i]); base1 = H * W; base2 = base1 + (H-1) * W; base3 = base2 + H * (W-1); total_nodes = base3 + (H-1) * (W-1); dist = (int*)malloc(total_nodes * sizeof(int)); queue = (int*)malloc(total_nodes * 2 * sizeof(int)); /* BFS queue, worst case each node once */ /* Use a simple BFS since all edges cost 1 */ /* But queue might need re-visits... actually BFS is fine since all costs are 1 */ for (int i = 0; i < total_nodes; i++) dist[i] = -1; int start = grid_id(0, 0); int goal = grid_id(H-1, W-1); dist[start] = 0; /* BFS with a queue */ /* Queue size: in worst case O(total_nodes) */ int qhead = 0, qtail = 0; /* We need queue of size total_nodes */ /* Realloc to be safe */ free(queue); queue = (int*)malloc(total_nodes * sizeof(int)); queue[qtail++] = start; #define PUSH(nd, d) do { \ if ((nd) >= 0 && (nd) < total_nodes && dist[nd] == -1) { \ dist[nd] = (d); \ queue[qtail++] = (nd); \ } \ } while(0) int di[] = {-1, 1, 0, 0}; int dj[] = {0, 0, -1, 1}; while (qhead < qtail) { int u = queue[qhead++]; int d = dist[u]; if (u < base1) { /* Grid node (i,j) */ int i = u / W, j = u % W; /* 4-directional moves within grid */ for (int dir = 0; dir < 4; dir++) { int ni = i + di[dir], nj = j + dj[dir]; if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue; if (!passable(ni, nj)) continue; PUSH(grid_id(ni, nj), d+1); } /* Enter row corridor above (between row i-1 and i) */ if (i > 0) PUSH(rowcor_id(i-1, j), d+1); /* Enter row corridor below (between row i and i+1) */ if (i < H-1) PUSH(rowcor_id(i, j), d+1); /* Enter col corridor left (between col j-1 and j) */ if (j > 0) PUSH(colcor_id(i, j-1), d+1); /* Enter col corridor right (between col j and j+1) */ if (j < W-1) PUSH(colcor_id(i, j), d+1); } else if (u < base2) { /* RowCorridor(r, j): between row r and r+1, at column j */ int tmp = u - base1; int r = tmp / W, j = tmp % W; /* Move horizontally along row corridor */ if (j > 0) PUSH(rowcor_id(r, j-1), d+1); if (j < W-1) PUSH(rowcor_id(r, j+1), d+1); /* Exit to grid above (row r) or below (row r+1) */ PUSH(grid_id(r, j), d+1); PUSH(grid_id(r+1, j), d+1); /* Enter col corridor to the left (between col j-1 and j) — intersection */ if (j > 0) PUSH(inter_id(r, j-1), d+1); /* Enter col corridor to the right (between col j and j+1) — intersection */ if (j < W-1) PUSH(inter_id(r, j), d+1); } else if (u < base3) { /* ColCorridor(i, c): between col c and c+1, at row i */ int tmp = u - base2; int i = tmp / (W-1), c = tmp % (W-1); /* Move vertically along col corridor */ if (i > 0) PUSH(colcor_id(i-1, c), d+1); if (i < H-1) PUSH(colcor_id(i+1, c), d+1); /* Exit to grid left (col c) or right (col c+1) */ PUSH(grid_id(i, c), d+1); PUSH(grid_id(i, c+1), d+1); /* Enter row corridor above (between row i-1 and i) — intersection */ if (i > 0) PUSH(inter_id(i-1, c), d+1); /* Enter row corridor below (between row i and i+1) — intersection */ if (i < H-1) PUSH(inter_id(i, c), d+1); } else { /* Intersection(r, c): row-gap r meets col-gap c */ int tmp = u - base3; int r = tmp / (W-1), c = tmp % (W-1); /* Move along row corridor (horizontally) */ if (c > 0) PUSH(inter_id(r, c-1), d+1); if (c < W-2) PUSH(inter_id(r, c+1), d+1); /* Move along col corridor (vertically) */ if (r > 0) PUSH(inter_id(r-1, c), d+1); if (r < H-2) PUSH(inter_id(r+1, c), d+1); /* Exit to RowCorridor(r, c) or RowCorridor(r, c+1) */ PUSH(rowcor_id(r, c), d+1); PUSH(rowcor_id(r, c+1), d+1); /* Exit to ColCorridor(r, c) or ColCorridor(r+1, c) */ PUSH(colcor_id(r, c), d+1); PUSH(colcor_id(r+1, c), d+1); } } printf("%d\n", dist[goal]); free(dist); free(queue); return 0; }