Untitled

 avatar
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