白駿17822号:ターンテーブル






問題の説明

  • https://www.acmicpc.net/problem/17822
  • の特定の円板を回転します.
  • を回転させた後、隣接する同じ数を削除します.
  • 隣接する
  • で同じ数が1つもない場合、平均より大きい数は1を減算し、平均より低い数は1を加算する.
  • 方法

  • 次元配列の回転で円盤を回転させる.
  • 同じ数の隣接データを
  • BFSで削除します.通常のBFSとは異なり、以下の点に注意してください.
  • 元なので、board[i][0]とboard[i][M]は隣接して処理すべきです.
  • ペアが存在する場合にのみ削除できます.
  • キューから取り出す場合は、0に変更するのではなく、同じ値がある場合は0に変更します.
  • pseudocode

    main(){
    	for(T){
        	TurnTable // 회전
            BFS // 같은 값 제거
            if(같은 값을 하나도 제거하지 못했으면){
            	평균보다 낮은 숫자는 +1, 평균보다 높은 숫자는 -1
            }
        }
    }
    
    BFS(start){
    	num = start좌표의 숫자
    	q.add(start)
    	while(q가 빌 때까지){
        	for(4방탐색을 진행){
            	원형이기 때문에 arr[x][0]에서 한 칸 왼쪽은 arr[x][M-1]
                원형이기 때문에 arr[x][M-1]에서 한 칸 오른쪽은 arr[x][0]
                if(board위에 있고 num과 같은 숫자라면){
                	q에 {nx,ny}삽입
                    똑같은 값을 제거(0으로 표시)
                }
            }
        }
    }
    

    正解

    import java.util.*;
    
    class Main {
    	static int[] dx = { 1, 0, -1, 0 };
    	static int[] dy = { 0, 1, 0, -1 };
    	static int N, M;
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		N = sc.nextInt();
    		M = sc.nextInt();
    		int T = sc.nextInt();
    		int[][] board = new int[N][M];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < M; j++) {
    				board[i][j] = sc.nextInt();
    			}
    		}
    
    		for (int t = 0; t < T; t++) {
    			int x = sc.nextInt();
    			int d = sc.nextInt();
    			int k = sc.nextInt();
    
    			// x의 배수인 행들을 돌립니다.
    			for (int i = 0; i < N; i++) {
    				if ((i + 1) % x != 0) continue;
    				board[i] = TurnTable(board[i], d, k);
    			}
    
    			
    			int BZeroCnt = 0;
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < M; j++) {
    					if (board[i][j] == 0) {
    						BZeroCnt++;
    					} else {
    						int[] temp = { i, j };
    						BFS(temp, board); // 모든 좌표에 대해 BFS를 실행합니다.
    					}
    				}
    			}
    
    			int AZeroCnt = 0;
    			int Sum = 0;
    			int Cnt = 0;
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < M; j++) {
    					if (board[i][j] == 0) {
    						AZeroCnt++;
    					} else {
    						Sum += board[i][j];
    						Cnt++;
    					}
    				}
    			}
    			
    			// BFS를 시도하기 이전의 0의 개수와 시도한 후 0의 개수가 같다는 건 아무런 제거가 없었다는 의미입니다.
    			if (BZeroCnt == AZeroCnt) {
    				for (int i = 0; i < N; i++) {
    					for (int j = 0; j < M; j++) {
    						if (board[i][j] == 0) continue;
    						double a = 1.0 * Sum / Cnt;
    						if (1.0 * board[i][j] > a) {
    							board[i][j]--;
    						} else if (1.0 * board[i][j] < a) {
    							board[i][j]++;
    						}
    					}
    				}
    			}
    
    		}
    		int ans = 0;
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < M; j++) {
    				ans += board[i][j];
    			}
    		}
    
    		System.out.println(ans);
    	}
    
    	public static int[] TurnTable(int[] arr, int d, int k) {
    		int size = arr.length;
    		int[] newArr = new int[size];
    
    		if (d == 0) { // 시계방향으로 회전합니다.
    			for (int i = 0; i < newArr.length; i++) {
    				newArr[i] = arr[(size + i - k) % size];
    			}
    		} else { // 반시계방향으로 회전합니다.
    			for (int i = 0; i < newArr.length; i++) {
    				newArr[i] = arr[(i + k) % size];
    			}
    
    		}
    		return newArr;
    	}
    
    	public static void BFS(int[] start, int[][] board) {
    		int num = board[start[0]][start[1]]; 
    		Queue<int[]> q = new LinkedList<int[]>();
    		q.add(start);		
    		while (!q.isEmpty()) {
    			int[] temp = q.poll();
    			for (int d = 0; d < 4; d++) {
    				int nx = temp[0] + dx[d];
    				int ny = temp[1] + dy[d];
    				// 행 데이터에 대해 원형인 걸 처리해줍니다.
    				if (ny == -1) ny = M - 1;
    				if (ny == M) ny = 0;
    				
    				if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == num) { 
    					int[] temp2 = { nx, ny };
    					q.add(temp2);
    					// 짝이 존재해야 0으로 제거가 가능합니다.
    					board[temp[0]][temp[1]] = 0;
    					board[nx][ny] = 0;
    				}
    			}
    		}
    	}
    
    }