algorithms software expert

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

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

목차

소프트웨어 익스퍼트 2105DFS

코드

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

public class SWE2105DFS {
    static int t, T, n, map[][] = new int[21][21], max;
    static int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -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());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while (T-- != 0) {
            n = Integer.parseInt(br.readLine());
            for (int i = 1; i <= n; i++) {
                int v = 1;
                st = new StringTokenizer(br.readLine(), " ");
                while (st.hasMoreTokens()) {
                    map[i][v++] = Integer.parseInt(st.nextToken());
                }
            }
            max = -1;
            boolean[] b = new boolean[101];
            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;
                    Arrays.fill(b, false);
                    Point s = new Point(i, j);
                    dfs(s, s, b, 0);
                }
            }
            sb.append("#");sb.append(t - T);
            sb.append(" ");sb.append(max);sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();bw.close();

    }

    private static void dfs(Point s, Point cur, boolean[] type, int d) {
        if (cur.x == s.x && cur.y == s.y && !cur.equals(s)) {
            int cnt = 0;
            for (int i = 0; i < 101; i++) {
                cnt += type[i] ? 1 : 0;
            }
            max = Math.max(max, cnt);
        }
        int nx, ny;
        for (int i = 0; i < 2; i++) {
            if (d + i == 4) continue;
            nx = cur.x + dx[d + i];
            ny = cur.y + dy[d + i];
            if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
            if (!type[map[nx][ny]]) {
                type[map[nx][ny]] = true;
                dfs(s, new Point(nx, ny), type, d + i);
                type[map[nx][ny]] = false;
            }
        }


    }

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

설명

Copied to clipboard