algorithms software expert

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

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

목차

소프트웨어 익스퍼트 1861

코드

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class SWE1861 {
    static int t, T, n, sx, sy;
    static int[][] map = new int[1001][1001];
    static String[] ins;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] visited = new boolean[1001][1001];
    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++) {
                ins = br.readLine().split(" ");
                for (int j = 1; j <= n; j++) {
                    map[i][j] = Integer.parseInt(ins[j - 1]);
                }
            }
            for (int i = 1; i <= n; i++) {
                Arrays.fill(visited[i], false);
            }
            int max = 0, maxX = 0, maxY = 0;
            map[0][0] = Integer.MAX_VALUE;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (visited[i][j]) continue;
                    int t = bfs(new Point(i, j, 1));
                    Point t2 = bfs2(new Point(i ,j, 0));
                    if (max < (t + t2.c)) {
                        max = (t + t2.c);maxX = t2.x;maxY = t2.y;
                    }else if (max == (t + t2.c) && map[maxX][maxY] > map[t2.x][t2.y]) {
                        maxX = t2.x;maxY = t2.y;
                    }
                }
            }

            bw.write("#" + (t - T) + " " + map[maxX][maxY] + " " + max + "\n");
            bw.flush();
        }
        bw.close();
    }

    public static int bfs(Point s) {
        Queue<Point> q = new LinkedList<>();
        q.offer(s);visited[s.x][s.y] = true;
        int lMax = 1;
        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i], ny = cur.y + dy[i];
                if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
                if (!visited[nx][ny] && map[nx][ny] - map[cur.x][cur.y] == 1) {
                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny, cur.c + 1));
                    lMax = Math.max(lMax, cur.c + 1);
                }
            }
        }
        return lMax;
    }

    public static Point bfs2(Point s) {
        Queue<Point> q = new LinkedList<>();
        q.offer(s);
        Point p = new Point();
        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i], ny = cur.y + dy[i];
                if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
                if (!visited[nx][ny] && map[nx][ny] - map[cur.x][cur.y] == -1) {
                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny, cur.c + 1));
                }
            }
            if (q.isEmpty()) p = cur;
        }
        return p;
    }

    private static class Point {
        int x, y, c;
        Point() {x = 0; y = 0; c= 0; }
        Point(int x, int y, int c) {
            this.x = x;this.y = y;this.c = c;
        }
    }

}

설명

Copied to clipboard