Submission #1172634
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 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 = 1;
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>>();
for (int n = 9; n >= 1; n--) {
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 (board[i][j] != n) continue;
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
Submission Time |
|
Task |
A - Multiple Pieces |
User |
suikkee |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
896834 |
Code Size |
3902 Byte |
Status |
AC |
Exec Time |
327 ms |
Memory |
31940 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
88227 / 1343058 |
84095 / 1343058 |
91944 / 1343058 |
84888 / 1343058 |
97542 / 1343058 |
86102 / 1343058 |
93207 / 1343058 |
83078 / 1343058 |
93841 / 1343058 |
93910 / 1343058 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
301 ms |
31368 KB |
subtask_01_02.txt |
AC |
288 ms |
29324 KB |
subtask_01_03.txt |
AC |
313 ms |
26084 KB |
subtask_01_04.txt |
AC |
282 ms |
27772 KB |
subtask_01_05.txt |
AC |
327 ms |
28020 KB |
subtask_01_06.txt |
AC |
321 ms |
26760 KB |
subtask_01_07.txt |
AC |
322 ms |
30632 KB |
subtask_01_08.txt |
AC |
292 ms |
30380 KB |
subtask_01_09.txt |
AC |
267 ms |
28340 KB |
subtask_01_10.txt |
AC |
289 ms |
31940 KB |