白駿17822号:ターンテーブル
35102 ワード
問題の説明
方法
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;
}
}
}
}
}
Reference
この問題について(白駿17822号:ターンテーブル), 我々は、より多くの情報をここで見つけました https://velog.io/@qwerty1434/백준-17822번-원판-돌리기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol