Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.9 kB
2
Indexable
Never
package T6;

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 class2 {
    static int n, m, cnt_exit;
    static int[][] arr = new int[105][105];
    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(int[][] arr, int m, int n, int cr, int cc) {
        int[][] timeToContaminate = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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 >= 1 && nr <= m && nc >= 1 && nc <= n && 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 = 1; i <= m; i++) {
            maxTime = Math.max(maxTime, timeToContaminate[i][1]);
        }

        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 = 1; r <= m; r++) {
                for (c = 1; c <= n; c++) {
                	arr[r][c]=scanner.nextInt();
                	if(arr[r][c]==2){
                		cr=r;
                		cc=c;
                	}
                }
            }

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