Untitled
unknown
plain_text
a year ago
4.0 kB
3
Indexable
import java.util.Scanner; public class Main { static int Answer = 9999; static int[][] region = new int[22][22]; static int[][] visited = new int[22][22]; static int N, C; static int[][] location = new int[5][2]; static int rear = -1; static int front = -1; static Queue[] Q = new Queue[10000]; static class Queue { int row; int col; Queue(int row, int col) { this.row = row; this.col = col; } } public static void init() { rear = -1; front = -1; for (int m = 0; m < 22; m++) { for (int n = 0; n < 22; n++) { visited[m][n] = 0; } } for (int m = 0; m < 10000; m++) { Q[m] = new Queue(0, 0); } } public static void discover(int row, int col, int val) { int cnt = 0; for (int k = 0; k < C; k++) { if (visited[location[k][0]][location[k][1]] > 0) { cnt++; } } if (cnt >= C) { return; } if ((row - 1) >= 1 && visited[row - 1][col] == 0 && (region[row - 1][col] == 1 || region[row - 1][col] == 3)) { visited[row - 1][col] = val + 1; ++rear; Q[rear] = new Queue(row - 1, col); } if ((row + 1) <= N && visited[row + 1][col] == 0 && (region[row + 1][col] == 1 || region[row + 1][col] == 3)) { visited[row + 1][col] = val + 1; ++rear; Q[rear] = new Queue(row + 1, col); } if ((col - 1) >= 1 && visited[row][col - 1] == 0 && (region[row][col - 1] == 1 || region[row][col - 1] == 3)) { visited[row][col - 1] = val + 1; ++rear; Q[rear] = new Queue(row, col - 1); } if ((col + 1) <= N && visited[row][col + 1] == 0 && (region[row][col + 1] == 1 || region[row][col + 1] == 3)) { visited[row][col + 1] = val + 1; ++rear; Q[rear] = new Queue(row, col + 1); } while (front < rear) { ++front; discover(Q[front].row, Q[front].col, visited[Q[front].row][Q[front].col]); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int test_case = 0; test_case < T; test_case++) { int x, y; int temp; Answer = 9999; N = sc.nextInt(); C = sc.nextInt(); for (int i = 0; i < C; i++) { x = sc.nextInt(); y = sc.nextInt(); location[i][0] = x; location[i][1] = y; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { region[i][j] = sc.nextInt(); } } for (int k = 0; k < C; k++) { region[location[k][0]][location[k][1]] = 3; } init(); Answer = 9999; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { init(); temp = 0; if (region[i][j] == 1) { visited[i][j] = 1; discover(i, j, 1); for (int k = 0; k < C; k++) { if (temp < visited[location[k][0]][location[k][1]]) { temp = visited[location[k][0]][location[k][1]]; } } if (Answer > temp) { Answer = temp; } } } } System.out.printf("#%d %d\n", test_case + 1, Answer - 1); } sc.close(); } }
Editor is loading...
Leave a Comment