algorithms software expert

소프트웨어 익스퍼트 1868 (software expert 1868)

소프트웨어 익스퍼트 1868 (software expert 1868)

목차

소프트웨어 익스퍼트 1868

코드

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;

public class SWE1868 {
    static int t, T, n;
    static char[][] map = new char[305][305];
    static int[][] isMine = new int[305][305];
    static String in;
    static PriorityQueue<Point> pq = new PriorityQueue<>();
    static int[] dx = {0, 0, -1, -1, -1, 1, 1, 1};
    static int[] dy = {1, -1, 0, 1, -1, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        t = T = Integer.parseInt(br.readLine());
        while (T-- != 0) {
            n = Integer.parseInt(br.readLine());
            for (int i = 1; i <= n; i++) {
                in = br.readLine();
                for (int j = 1; j <= n; j++) {
                    map[i][j] = in.charAt(j - 1);
                }
            }
            pq.clear();
            countMine();
            int count = 0;
            while (!pq.isEmpty()) {
                Point cur = pq.peek();
                if (map[cur.x][cur.y] == '.') {
                    click(pq.poll());count++;
                } else pq.poll();
            }
            bw.write("#" + (t - T) + " " + count + "\n");
            bw.flush();
        }
        bw.close();
    }

    public static void countMine() {
        for (int i = 1; i <= n; i++) {
            Arrays.fill(isMine[i], 0);
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k < 8; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (map[nx][ny] == '*') {
                        isMine[i][j]++;
                    }
                }
                pq.offer(new Point(i, j, isMine[i][j]));
            }
        }
    }

    public static void click(Point p) {
        if (p.c == 0) {
            for (int k = 0; k < 8; k++) {
                int nx = p.x + dx[k];
                int ny = p.y + dy[k];
                if (nx < 1 || nx > n || ny < 1 || ny > n || map[nx][ny] != '.') continue;
                map[nx][ny] = (char)(isMine[nx][ny] + 48);
                click(new Point(nx, ny, isMine[nx][ny]));
            }
        }else {
            map[p.x][p.y] = (char)(isMine[p.x][p.y] + 48);
        }
    }


    private static class Point implements Comparable<Point>{
        int x, y, c;
        Point(int x, int y, int c) {
            this.x = x;this.y = y;this.c = c;
        }
        @Override
        public int compareTo(Point p) {
            return c > p.c ? 1 : -1;
        }
    }
}

설명