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