Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.8 kB
1
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

class queue {
    static int[] Data = new int[400];
    static int front, rear;

    public queue() {
        this.front = this.rear = -1;
    }

    void reset() {
        front = rear = -1;
    }

    public void enQueue(int value) {
        Data[++rear] = value;
    }

    int deQueue() {
        return Data[++front];
    }

    boolean isEmpty() {
        if (this.front == this.rear) {
            return true;
        }
        return false;
    }
}

public class Bai4 {
    static int n, m, cnt_exit;
    static char[][] arr = new char[20][20];
    static int[] spinR = { 0, 0, 1, -1 };
    static int[] spinC = { 1, -1, 0, 0 };
    static int cr, cc, nr, nc, r, c;
    static boolean ans = false;

    static int spreadContamination(char[][] arr, int n, int m, int cr, int cc) {
        int[][] timeToContaminate = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                timeToContaminate[i][j] = -1;
            }
        }

        queue rqueue = new queue();
        queue cqueue = new queue();

        timeToContaminate[cr][cc] = 0;
        rqueue.enQueue(cr);
        cqueue.enQueue(cc);

        while (!rqueue.isEmpty()) {
            int r = rqueue.deQueue();
            int c = cqueue.deQueue();

            for (int k = 0; k < 4; k++) {
                int nr = r + spinR[k];
                int nc = c + spinC[k];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m && arr[nr][nc] == '1' && timeToContaminate[nr][nc] == -1) {
                    timeToContaminate[nr][nc] = timeToContaminate[r][c] + 1;
                    rqueue.enQueue(nr);
                    cqueue.enQueue(nc);
                }
            }
        }

        int maxTime = 0;
        for (int i = 0; i < n; i++) {
            maxTime = Math.max(maxTime, timeToContaminate[i][0]);
        }

        return maxTime;
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("Text"));
        Scanner scanner = new Scanner(System.in);
        int tc = scanner.nextInt();
        for (int Case = 1; Case <= tc; Case++) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            queue rqueue = new queue();
            queue cqueue = new queue();

            for (r = 0; r < n; r++) {
                String row = scanner.next();
                for (c = 0; c < m; c++) {
                    arr[r][c] = row.charAt(c);
                    if (arr[r][c] == '2') {
                        cr = r;
                        cc = c;
                    }
                }
            }

            int time = spreadContamination(arr, n, m, cr, cc);
            System.out.println(time);
        }
    }
}