Submission #1172668

---

Source Code Expand

import java.util.*;

public class Main {
    //-------------------------------------------------------------//
    public static final void main(String[] args) {
        new Main().solve();
    }

    //-------------------------------------------------------------//
    private final int dx4[] = {0, 1, 0, -1};
    private final int dy4[] = {-1, 0, 1, 0};
    private final int dx8[] = {0, 1, 1, 1, 0, -1, -1, -1};
    private final int dy8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    //-------------------------------------------------------------//
    //private final long TIME_LIMIT = 9800;
    //private final long START_TIME = System.currentTimeMillis();

    private final Scanner sc = new Scanner(System.in);
    private final int W = 50;
    private final int H = 50;
    private final int K = 8;
    private int[][] board = new int[H][W];
    private Pos[][] P = new Pos[H][W];
    boolean[][] used = new boolean[H][W];

    void input() {
        sc.nextLine();
        for (int i = 0; i < H; i++) {
            String[] row = sc.next().split("");
            for (int j = 0; j < W; j++) {
                board[i][j] = Integer.parseInt(row[j]);
                P[i][j] = new Pos(j, i);
            }
        }
    }

    int makePiece(Pos cp, List<Pos> result) {
        boolean retry = true;
        int score = board[cp.y][cp.x];
        result.add(cp);
        while (retry && result.size() < K) {
            retry = false;
            int maxNumber = 0;
            Pos maxNumberPos = null;
            for (Pos p : result) {
                for (int i = 0; i < 4; i++) {
                    int x = p.x + dx4[i];
                    int y = p.y + dy4[i];
                    if (x >= 0 && x < W && y >= 0 && y < H) {
                        if (used[y][x]) continue;
                        if (board[y][x] > maxNumber && !result.contains(P[y][x])) {
                            maxNumber = board[y][x];
                            maxNumberPos = P[y][x];
                        }
                    }
                }
            }
            if (maxNumberPos != null) {
                retry = true;
                score *= maxNumber;
                result.add(maxNumberPos);
            }
        }

        return score;
    }

    void solve() {
        input();
        List<List<Pos>> res = new ArrayList<List<Pos>>();
        boolean retry = true;
        while (retry) {
            retry = false;
            int maxScore = 0;
            List<Pos> maxScorePiece = null;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (used[i][j]) continue;
                    List<Pos> piece = new ArrayList<Pos>(K);
                    int score = makePiece(P[i][j], piece);
                    if (piece.size() != K) continue;
                    if (score > maxScore) {
                        maxScore = score;
                        maxScorePiece = piece;
                    }
                }
            }
            if (maxScorePiece != null) {
                retry = true;
                res.add(maxScorePiece);
                for (Pos p : maxScorePiece) {
                    used[p.y][p.x] = true;
                }
            }
        }

        System.out.println(res.size());
        for (List<Pos> list : res) {
            for (Pos p : list) {
                System.out.println((p.y + 1) + " " + (p.x + 1));
            }
        }
    }
}

class Pos {
    final int x, y;

    Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object obj) {
        Pos p = (Pos) obj;
        if (x != p.x) return false;
        if (y != p.y) return false;
        return true;
    }
}

Submission Info

Judge Result