9.20度小满第二个编程
在交卷之后做出来了。。。
dfs只能通过9%,因为普通'.'格子是不计算步数的。
package duxiaoman; import org.omg.CORBA.INTERNAL; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Main2 { static int[] dx = {1,0,-1,0}; static int[] dy = {0,1,0,-1}; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(reader.readLine()); for (int i = 0; i < n; i++) { String[] s = reader.readLine().split(" "); int l0 = Integer.parseInt(s[0]); int l1 = Integer.parseInt(s[1]); int[][] map = new int[l0][l1]; int[][] dis = new int[l0][l1]; int[] start = new int[2]; for (int j = 0; j < map.length; j++) { String str = reader.readLine(); for (int k = 0; k < str.length(); k++) { char c = str.charAt(k); if (c == '#'){ map[j][k] = 3; }else if (c == '*'){ map[j][k] = 1; }else if (c == '.'){ map[j][k] = 0; }else if (c == '@'){ start[0] = j; start[1] = k; } dis[j][k] = Integer.MAX_VALUE; } } dis[start[0]][start[1]] = 0; map[start[0]][start[1]] = 0; boolean[][] flag = new boolean[l0][l1]; flag[start[0]][start[1]] = true; while (true){ int sum0 = zou0(map,flag,dis); int sum1 = zou1(map,flag,dis); if (sum0 + sum1 == 0) { break; } } int res = Integer.MAX_VALUE; for (int j = 0; j < l1; j++) { int t = Math.min(dis[0][j],dis[l0-1][j]); if (t < res){ res = t; } } for (int j = 0; j < l0; j++) { int t = Math.min(dis[j][0],dis[j][l0-1]); if (t < res){ res = t; } } if (res == Integer.MAX_VALUE){ System.out.println(-1); }else { System.out.println(res); } } } public static int zou0(int[][] map,boolean[][] flag,int[][] dis){ int c = 0; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { if (map[i][j] == 0 && !flag[i][j]){ for (int k = 0; k <4; k++) { int tx = i + dx[k]; int ty = j + dy[k]; if (tx >= 0 && tx < map.length && ty >= 0 && ty < map[1].length && flag[tx][ty]){ dis[i][j] = dis[tx][ty]; flag[i][j] = true; c++; } } } } } return c; } public static int zou1(int[][] map,boolean[][] flag,int[][] dis){ int c = 0; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { if (map[i][j] == 1 && !flag[i][j]){ for (int k = 0; k <4; k++) { int tx = i + dx[k]; int ty = j + dy[k]; if (tx >= 0 && tx < map.length && ty >= 0 && ty < map[1].length && flag[tx][ty]){ dis[i][j] = dis[tx][ty] + 1; flag[i][j] = true; c++; } } } } } return c; } } /* 1 3 4 #### #@.* **.* */