import java.io.*; import java.util.*; public class Main { static int N, M; static int score = 0; static int[][] directions = {{-1,0},{0,1},{1,0},{0,-1}}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); int[][] board = new int[N][N]; for (int i = 0; i < N; i ++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j ++) { board[i][j] = Integer.parseInt(st.nextToken()); } } while (true) { int[] cur = getGroup(board); if (cur[0] == -1) break; deleteGroup(board, cur[0], cur[1]); gravity(board); reverseClock(board); gravity(board); } System.out.print(score); br.close(); } public static String beautifulPrint(int[][] board) { StringBuilder sb = new StringBuilder(""); for (int i = 0; i < N; i ++) { sb.append(Arrays.toString(board[i])).append("\n"); } return sb.toString(); } public static void reverseClock (int[][] board) { int[][] nextBoard = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j ++) { nextBoard[N-1-j][i] = board[i][j]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j ++) { board[i][j] = nextBoard[i][j]; } } } public static void gravity (int[][] board) { for (int i = N-2; i >= 0; i --) { for (int j = N-1; j >= 0; j --) { if (board[i][j] != -1 && board[i][j] != -2) { int ci = i; while (ci+1 < N && board[ci+1][j] == -2) { ci ++; } if (ci != i && ci < N) { board[ci][j] = board[i][j]; board[i][j] = -2; } } } } } public static void deleteGroup (int[][] board, int si, int sj) { LinkedList queue = new LinkedList<>(); queue.add(new int[]{si, sj}); int[][] visited = new int[N][N]; visited[si][sj] = board[si][sj]; while (!queue.isEmpty()) { int[] cur = queue.poll(); for (int[] dir : directions) { int ni = cur[0] + dir[0], nj = cur[1] + dir[1]; if (0 <= ni && ni < N && 0 <= nj && nj < N) { if (visited[ni][nj] == 0) { if (board[ni][nj] == board[si][sj] || board[ni][nj] == 0) { queue.add(new int[]{ni, nj}); visited[ni][nj] = board[si][sj]; } } } } } int cnt = 0; for (int i = 0; i < N; i ++) { for (int j = 0; j < N; j ++) { if (visited[i][j] != 0) { board[i][j] = -2; // -2 : emptySpace cnt ++; } } } score += cnt*cnt; } public static int[] getGroup (int[][] board) { int gi = -1, gj = -1; int groupSize = 0; int rainbowCnt = 0; boolean[][] baseVisited = new boolean[N][N]; for (int i = 0; i < N; i ++) { for (int j = 0; j < N; j ++) { if (board[i][j] > 0 && !baseVisited[i][j]) { int[] cur = divideGroup(baseVisited, board, i, j); if (cur[0] >= 2) { if (groupSize < cur[0]) { groupSize = cur[0]; rainbowCnt = cur[1]; gi = i; gj = j; } else if (groupSize == cur[0]) { if (rainbowCnt < cur[1]) { rainbowCnt = cur[1]; gi = i; gj = j; } else if (rainbowCnt == cur[1]) { gi = i; gj = j; } } } } } } return new int[]{gi, gj}; } public static int[] divideGroup (boolean[][] baseVisited, int[][] board, int si, int sj) { LinkedList queue = new LinkedList<>(); queue.add(new int[]{si, sj}); baseVisited[si][sj] = true; int[][] visited = new int[N][N]; visited[si][sj] = board[si][sj]; int rainbowCnt = 0; int curGroupSize = 1; while (!queue.isEmpty()) { int[] cur = queue.poll(); for (int[] dir : directions) { int ni = cur[0] + dir[0], nj = cur[1] + dir[1]; if (0 <= ni && ni < N && 0 <= nj && nj < N) { if (visited[ni][nj] == 0) { if (board[ni][nj] == board[si][sj] || board[ni][nj] == 0) { queue.add(new int[]{ni, nj}); visited[ni][nj] = board[si][sj]; baseVisited[ni][nj] = true; rainbowCnt += board[ni][nj] == 0 ? 1 : 0; curGroupSize++; } } } } } return new int[]{curGroupSize, rainbowCnt}; } }

코드 #2913