Untitled

package BattleCity;

import java.io.FileInputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Solution {
    static int n,m,xbegin,ybegin,xend,yend,front,rear,ans;;
    static int[][] a,d;
    static  int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
    static Position[] pQ;
    final static int BRICK = 2,TARGET = 3, EMPTY = 1;
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("input.txt"));
        System.setOut(new PrintStream("output.txt"));
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            n = sc.nextInt();
            m = sc.nextInt();
            a = new int[n][m];
            d = new int[n][m];
            for(int i=0;i<n;i++){
                String s = sc.next();
                for(int j=0;j<m;j++){
                    switch (s.charAt(j)){
                        case 'Y':
                            xbegin = i;
                            ybegin = j;
                            a[i][j] = 0;
                            break;
                        case 'T':
                            xend = i;
                            yend = j;
                            a[i][j] = TARGET;
                            break;
                        case 'B':
                            a[i][j] = BRICK;
                            break;
                        case 'E':
                            a[i][j] = EMPTY;
                            break;
                        default:
                            a[i][j] = -1;
                    }
                }
            }
            ans = Integer.MAX_VALUE;
            Position begin = new Position(xbegin,ybegin,0);
            pQ = new Position[n*m];
            BFS(begin);
            System.out.println("Case #"+t);
            if(ans==Integer.MAX_VALUE){
                System.out.println(-1);
            }
            else {
                System.out.println(ans);
            }
        }
    }
    static void BFS(Position p){
        front = 0;
        rear = 0;
        pQ[rear++] = p;
        d[p.x][p.y] = 1;
        while (front<rear){
            Position u = pop();
            if(u.x==xend&&u.y==yend){
                ans = Math.min(ans,d[u.x][u.y]-1);
                break;
            }
            for(int i=0;i<4;i++){
                int xx = u.x+dx[i];
                int yy = u.y+dy[i];
                if(xx>=0&&xx<n&&yy>=0&&yy<m){
                    if(d[xx][yy]==0){
                        if(a[xx][yy]==BRICK){
                            d[xx][yy] = d[u.x][u.y] + 2;
                            pQ[rear++] = new Position(xx,yy,d[xx][yy]);
                        }
                        if(a[xx][yy]==TARGET||a[xx][yy]==EMPTY){
                            d[xx][yy] = d[u.x][u.y] + 1;
                            pQ[rear++] = new Position(xx,yy,d[xx][yy]);
                        }
                    }
                }
            }
        }
    }
    static Position pop(){
        int min = pQ[front].distance;
        int index = front;
        for(int i=front+1;i<rear;i++){
            if(min>pQ[i].distance){
                min = pQ[i].distance;
                index = i;
            }
        }
        Position tmp = pQ[front];
        pQ[front] = pQ[index];
        pQ[index] = tmp;
        return pQ[front++];
    }
    static class Position{
        int x;
        int y;
        int distance;

        public Position(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
}
package GridAcid;

import java.io.FileInputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Solution {
    static int n,m;
    static int[][] a,d;
    static int[] dx = {-1,1,0,0},dy = {0,0,-1,1},q;
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("input.txt"));
        System.setOut(new PrintStream("output.txt"));
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for(int t = 1;t<=tc;t++){
            n = sc.nextInt();
            m = sc.nextInt();
            a = new int[n][m];
            q = new int[n*m];
            d = new int[n][m];
            int x_acid = sc.nextInt()-1;
            int y_acid = sc.nextInt()-1;
            int x_cell = -1;
            int y_cell = -1;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    a[i][j] = sc.nextInt();
                    if(a[i][j]==2){
                        x_cell = i;
                        y_cell = j;
                    }
                }
            }
            BFS(x_acid,y_acid);
            System.out.println("Case #"+t);
            System.out.println(x_cell+" "+y_cell);
            System.out.println(count1(x_cell,y_cell)+" "+count2());
        }
    }
    static void BFS(int r,int c){
        int head = -1,tail = -1;
        q[++tail] = r*m+c;
        d[r][c] = 1;
        while (head<tail){
            int pop = q[++head];
            int x = pop/m;
            int y = pop%m;
            for(int i=0;i<4;i++){
                int xx = x+dx[i];
                int yy = y+dy[i];
                if(xx>=0&&xx<n&&yy>=0&&yy<m){
                    if(a[xx][yy]==1&&d[xx][yy]==0){
                        d[xx][yy] = d[x][y]+1;
                        q[++tail] = xx*m+yy;
                    }
                }
            }

        }
    }
    static int count2(){
        int ans = -1;
        for(int i = 0;i<n;i++){
            for(int j=0;j<m;j++){
                if(a[i][j]==1&&d[i][j]==0) return -1;
                ans = Math.max(d[i][j],ans);
            }
        }
        return ans;
    }
    static int count1(int x,int y){
        int ans = -1;
        for(int i=0;i<4;i++){
            int xx = x+dx[i];
            int yy = y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m) {
                if (d[xx][yy] == 0) return -1;
                ans = Math.max(ans, d[xx][yy]);
            }
        }
        return ans;
    }
}