网站建设求职综合商城网站程序
Problem F. 幻形之路
给定一个 n × m n×m n×m 的迷宫，每个格子为 . （空地）或 #（障碍）。你从左上角 ( 1 , 1 ) (1,1) (1,1) 出发，目标是到达右下角 ( n , m ) (n,m) (n,m) ，每步可以向上、下、左、右移动一格，不能移动到迷宫外部，也不能移动到障碍格子上。
你可以选择 至多一次 服用一种药剂，在服药后的连续 k （ k ≥ 0 ） k（k ≥0） k（k≥0）步中，你可以将障碍视为可以通行的空地。
请你计算从起点到终点可达的前提下，所需的最小 k k k 值是多少。
输入格式
本题包含多组测试数据
第一行一个正整数 T （ 1 ≤ T ≤ 2.5 × 105 ） T（1≤T ≤2.5×105） T（1≤T≤2.5×105） ，表示测试数据的组数。
对于每组数据：
第一行两个正整数 n , m （ 2 ≤ n , m ≤ 1000 ） n,m（2≤n,m≤1000） n,m（2≤n,m≤1000） ，表示迷宫的大小。
接下来一个 n × m n×m n×m 的矩阵，表示迷宫。保证起点和终点不为障碍
保证所有数据的 ∑ n m ≤ 10 6 ∑nm≤10^6 ∑nm≤106 。
输出格式
对于每组数据，输出一行，表示k的最小值。
样例输入
2
3 4
..##
###.
.##.
3 2
..
##
..
样例输出
2
1
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;public class Main {static final int[] dx = {-1, 1, 0, 0};static final int[] dy = {0, 0, -1, 1};// Function to perform BFS and mark reachable pointsstatic void bfs(String[] grid, int[][] dist, boolean[][] reachable, int start_i, int start_j) {int n = grid.length;int m = grid[0].length();Queue<int[]> q = new LinkedList<>();q.add(new int[]{start_i, start_j});reachable[start_i][start_j] = true;while (!q.isEmpty()) {int[] current = q.poll();int i = current[0];int j = current[1];for (int d = 0; d < 4; ++d) {int ni = i + dx[d];int nj = j + dy[d];if (ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni].charAt(nj) == '.' && !reachable[ni][nj]) {reachable[ni][nj] = true;q.add(new int[]{ni, nj});}}}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (reachable[i][j]) {dist[i][j] = 0;q.add(new int[]{i, j});}}}while (!q.isEmpty()) {int[] current = q.poll();int i = current[0];int j = current[1];for (int d = 0; d < 4; ++d) {int ni = i + dx[d];int nj = j + dy[d];if (ni >= 0 && ni < n && nj >= 0 && nj < m && dist[ni][nj] > dist[i][j] + 1) {dist[ni][nj] = dist[i][j] + 1;q.add(new int[]{ni, nj});}}}}public static void main(String[] args) throws IOException {BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));int T = Integer.parseInt(bf.readLine());while (T-- > 0) {String[] str = bf.readLine().split(" ");int n = Integer.parseInt(str[0]);int m = Integer.parseInt(str[1]);String[] grid = new String[n];for (int i = 0; i < n; ++i) {grid[i] = bf.readLine();}// Step 1: Find start_reachable and end_reachable pointsboolean[][] startReachable = new boolean[n][m];boolean[][] endReachable = new boolean[n][m];int[][] distStart = new int[n][m];int[][] distEnd = new int[n][m];for (int i = 0; i < n; ++i) {Arrays.fill(distStart[i], Integer.MAX_VALUE);Arrays.fill(distEnd[i], Integer.MAX_VALUE);}// Step 2: Multi-source BFS for start and end reachable pointsbfs(grid, distEnd, startReachable, 0, 0);bfs(grid, distStart, endReachable, n - 1, m - 1);// Step 3: Calculate the answerint answer = Integer.MAX_VALUE;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (distStart[i][j] != -1 && distEnd[i][j] != -1) {answer = Math.min(answer, distStart[i][j] + distEnd[i][j] - 1);}}}bw.write(Math.max(answer, 0) + "\n");bw.flush();}bw.close();}
}