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
####
#@.* **.*
*/
