algorithms software expert

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

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

소프트웨어 익스퍼트 2105

코드

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

public class SWE2105 {
    static int t, T, n;
    static int[][] map = new int[21][21];
    static String ins[];
    static int[] dx = {1, 1, -1, -1};
    static int[] dy = {1, -1, -1, 1};
    final static int RD = 0, LD = 1, LU = 2, RU = 3;
    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]);
                }
            }
            int max = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (j + 1 > n || j - 1 < 1 || i + 2 > n) continue;
                    boolean[] dessert = new boolean[101];
                    max = Math.max(max, bfs(new Point(i, j, RD, 0, dessert)));
                }
            }

            bw.write("#" + (t - T) + " " + ((max == 0) ? -1 : max)  + "\n");
            bw.flush();
        }
        bw.close();
    }

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

    private static class Point {
        int x, y, d, c;
        boolean[] dessert = new boolean[101];
        Point(int x, int y, int d, int c, boolean[] dessert) {
            this.x = x;this.y = y;this.d = d; this.c = c;
            System.arraycopy(dessert, 0, this.dessert, 0, 101);
        }
    }
}

설명

Copied to clipboard