Untitled
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); } } }