度小满 9.20笔试

package 度小满_2020_9_20.二;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int nnn=in.nextInt();
        for (int q = 0; q < nnn; q++) {
            int n=in.nextInt(),m=in.nextInt();
            char[][] a=new char[n][m];
            for (int i = 0; i < n; i++) {
                String s=in.next();
                char[] sctmp=s.toCharArray();
                for (int i1 = 0; i1 < sctmp.length; i1++) {
                    a[i][i1]=sctmp[i1];
                }
            }

            int[][] b=new int[n][m];//b[i][j]表示当前格子的最小破壁次数，Integer.MAX_VALUE表示无法破壁
            for (int i = 0; i < b.length; i++) {
                for (int j = 0; j < b[0].length; j++) {
                    b[i][j]=Integer.MAX_VALUE;
                }
            }
            int[][] c=new int[n][m];//记录当前格子是否被访问过
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[0].length; j++) {
                    if(a[i][j]=='@'){
                        new Main().dfs(a,b,c,n,m,i,j,0);
                        System.out.println(b[i][j]==Integer.MAX_VALUE?-1:b[i][j]);
                        break;
                    }
                }
            }


        }

    }
    /*
    "@"代表小昆虫的初始位置，"."代表可以通过的空地，"*"代表可以破坏的障碍物，"#"代表不可破坏的障碍物
     */
    public int dfs(char[][] a,int[][] b,int[][] c,int n,int m,int i,int j,int use){
        int use_new=use;
        if(i>=n||i<0||j>=m||j<0) {
            return 0;
        }
        if(b[i][j]!=Integer.MAX_VALUE&&b[i][j]<=use_new) return b[i][j];
        if(c[i][j]==1) return Integer.MAX_VALUE;
        if(a[i][j]=='#') return Integer.MAX_VALUE;
        if(a[i][j]=='*'){
            use_new++;
        }
        c[i][j]=1;
        int i1=dfs(a,b,c,n,m,i+1,j,use_new);
        int i2=dfs(a,b,c,n,m,i-1,j,use_new);
        int i3=dfs(a,b,c,n,m,i,j+1,use_new);
        int i4=dfs(a,b,c,n,m,i,j-1,use_new);
        c[i][j]=0;
        int min=Math.min(b[i][j],Math.min(Math.min(i1,i2),Math.min(i3,i4)));
        if(a[i][j]=='*'){
            min+=1;
        }
        b[i][j]=Math.min(b[i][j],min);
        return b[i][j];
    }
}