Submission #1151278

---

Source Code Expand

import java.util.*;

public class Main {
    private static final int[] DR = {1, 0, -1, 0};
    private static final int[] DC = {0, 1, 0, -1};
    static Scanner sc = new Scanner(System.in);
    static SplittableRandom rnd = new SplittableRandom();
    static long[][] hash;
    static int H, W, K;
    static int[][] f;
    static boolean[][] used;
    static ArrayList<Piece> pieces = new ArrayList<>();
    static ArrayList<HashSet<Long>> usedHashes = new ArrayList<>();

    public static void main(String[] args) {
        H = sc.nextInt();
        W = sc.nextInt();
        K = sc.nextInt();
        f = new int[H][W];
        used = new boolean[H][W];
        hash = new long[H][W];
        for (int i = 0; i < H; i++) {
            String row = sc.next();
            for (int j = 0; j < W; j++) {
                f[i][j] = row.charAt(j) - '0';
                hash[i][j] = ((long) rnd.nextInt() << 32) | rnd.nextInt();
                if (f[i][j] == 0) used[i][j] = true;
            }
        }
        for (int i = 0; i <= K; i++) {
            usedHashes.add(new HashSet<>());
        }
        enumerate();
        System.err.println(pieces.size());
        Collections.sort(pieces);

        for (int i = 0; i < H; i++) {
            Arrays.fill(used[i], false);
        }
        ArrayList<Piece> usedPieces = new ArrayList<>((int) (0.85 * H * W / K));
        for (int i = pieces.size() - 1; i >= 0; i--) {
            boolean ok = true;
            Piece p = pieces.get(i);
            for (int j = 0; j < K; j++) {
                if (used[p.y[j]][p.x[j]]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                usedPieces.add(p);
                for (int j = 0; j < K; j++) {
                    used[p.y[j]][p.x[j]] = true;
                }
            }
        }
        System.out.println(usedPieces.size());
        for (Piece piece : usedPieces) {
            for (int i = 0; i < K; i++) {
                System.out.println((piece.y[i] + 1) + " " + (piece.x[i] + 1));
            }
        }
    }

    static void enumerate() {
        int[] x = new int[K];
        int[] y = new int[K];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                x[0] = j;
                y[0] = i;
                if (f[i][j] == 0) continue;
                used[i][j] = true;
                for (int k = 1; k <= K; k++) {
                    usedHashes.get(k).clear();
                }
                dfs(x, y, hash[i][j], f[i][j], 1);
            }
        }
    }

    static void dfs(int[] x, int[] y, long h, int score, int depth) {
        for (int i = 0; i < depth; i++) {
            for (int j = 0; j < 4; j++) {
                int nr = y[i] + DR[j];
                int nc = x[i] + DC[j];
                if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
                if (used[nr][nc]) continue;
                long nextHash = h ^ hash[nr][nc];
                if (usedHashes.get(depth).contains(nextHash)) continue;
                usedHashes.get(depth).add(nextHash);
                x[depth] = nc;
                y[depth] = nr;
                if (depth == K - 1) {
                    pieces.add(new Piece(x, y, score * f[nr][nc]));
                    continue;
                }
                used[nr][nc] = true;
                dfs(x, y, nextHash, score * f[nr][nc], depth + 1);
                used[nr][nc] = false;
            }
        }
    }

    static class Piece implements Comparable<Piece> {
        int[] x, y;
        int score;

        public Piece(int[] x, int[] y, int score) {
            this.x = x.clone();
            this.y = y.clone();
            this.score = score;
        }

        @Override
        public int compareTo(Piece o) {
            return Integer.compare(this.score, o.score);
        }
    }
}

Submission Info

Judge Result