白駿21610号:魔法使いサメと琵琶魚






問題の説明

  • https://www.acmicpc.net/problem/21610
  • リンクには、上記の図よりも詳細な画像説明が含まれています.地上関係で省略したので
  • は、所与の条件下で実施される問題である.
  • 方法

  • の2 Dアレイでナビゲートする場合は、次の2点に注意してください.
  • の範囲を超えると、逆方向の方法
  • に戻る.
  • d方向が負の場合にインデックスを処理する方法
  • .
  • の条件を満たす値を取得する場合は、すぐに値を変更するか、保存して一度に処理するかを考慮する必要があります.
    すぐに
  • コピー部分からコピーすると、別の対角線バスケットの値に影響しますので、一緒に処理する必要があります.
  • pseudocode

    정확도를 측정하기 위해 메서드 구현 없이 풀어봤습니다.
    메서드로 구현하는 게 디버깅에 엄청난 시간단축이 됩니다.
    메서드 구현이 아니므로 각 구간에 대한 설명은 정답코드의 주석으로 대신하겠습니다.

    正解

    import java.util.*;
    
    public class Main {
    	static int[][] board;
    	static int[] dx = { 0, -1, -1, -1, 0, 1, 1, 1 };
    	static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt();
    		int M = sc.nextInt();
    		board = new int[N][N];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				board[i][j] = sc.nextInt();
    			}
    		}
    		// 최초 생성된 구름입니다.
    		List<pos> CloudLst = new ArrayList<pos>();
    		CloudLst.add(new pos(N - 1, 0));
    		CloudLst.add(new pos(N - 2, 0));
    		CloudLst.add(new pos(N - 1, 1));
    		CloudLst.add(new pos(N - 2, 1));
    
    		for (int m = 0; m < M; m++) { // M번의 이동이 발생합니다.
    			boolean[][] v = new boolean[N][N];
    			int d = sc.nextInt(); 
    			d--; // d는 1~8로 들어오기 때문에 인덱스로 활용하기 위해 -1을 실행합니다.
    			int s = sc.nextInt();
    			int size = CloudLst.size();
    			List<pos> CheckLst = new ArrayList<pos>();
    
    			// 구름 이동
    			for (int idx = 0; idx < size; idx++) {
    				pos c = CloudLst.remove(0);
    				int nx = c.x;
    				int ny = c.y;
    				
    				// d방향으로 s만큼 움직입니다.
    				for (int i = 0; i < s; i++) {
    					// dx가 마이너스라서 음수가 나오는 걸 방시하기위해 0이될때마다 새롭게 N을 더해줍니다.
    					if (nx == 0) {
    						nx += N;
    					}
    
    					if (ny == 0) {
    						ny += N;
    					}
    
    					nx = (nx + dx[d]) % N;
    					ny = (ny + dy[d]) % N;
    				}
    
    //				int nx = (N*N*N+c.x+dx[d]*s)%N;
    //				int ny = (N*N*N+c.y+dy[d]*s)%N;
    				
    				v[nx][ny] = true; // 이번에 구름이 위치한 곳에서는 다음 구름이 발생하지 않습니다.
    				board[nx][ny] += 1;
    				CheckLst.add(new pos(nx, ny));
    			}
    
    //			System.out.println("구름 이동");
    //			for (int i = 0; i < N; i++) {
    //				System.out.println(Arrays.toString(board[i]));
    //			}			
    
    			// 물복사
    			for (int c = 0; c < CheckLst.size(); c++) {
    				int cnt = 0;
    				for (int d2 = 0; d2 < 8; d2++) {
    					if (d2 % 2 == 0)
    						continue;
    					int nx = CheckLst.get(c).x + dx[d2];
    					int ny = CheckLst.get(c).y + dy[d2];
    					if (0 <= nx && nx < N && 0 <= ny && ny < N && board[nx][ny] != 0) { // 구름의 이동과 다르게 경계를 넘어갈 수 없습니다.
    						cnt++;
    					}
    				}
    				board[CheckLst.get(c).x][CheckLst.get(c).y] += cnt;
    			}
    
    //			System.out.println("물복사");
    //			for (int i = 0; i < N; i++) {
    //				System.out.println(Arrays.toString(board[i]));
    //			}
    
    			// 구름생성
    			for (int i = 0; i < N; i++) {
    				for (int j = 0; j < N; j++) {
    					if (board[i][j] >= 2 && !v[i][j]) {
    						CloudLst.add(new pos(i, j));
    						board[i][j] -= 2;
    					}
    				}
    			}
    
    //			System.out.println("구름생성");
    //			for (int i = 0; i < N; i++) {
    //				System.out.println(Arrays.toString(board[i]));
    //			}
    
    		}
    		
    		// 최종 점수를 계산합니다
    		int Score = 0;
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				Score += board[i][j];
    			}
    		}
    		System.out.println(Score);
    	}
    
    	static class pos {
    		int x;
    		int y;
    
    		@Override
    		public String toString() {
    			return "pos [x=" + x + ", y=" + y + "]";
    		}
    
    		public pos(int x, int y) {
    			super();
    			this.x = x;
    			this.y = y;
    		}
    
    	}
    }

    その他


    ネガティブインデックス


    d方向移動sの場合
  • 元のやり方:Nの倍数を加える.
  • 問題点:Nの倍数をいくら加えるか分からない.StackOverFlowリスク
  • 例)魔法使いサメと火球2
  • 新方式:1に1を加え、0にNを加える.
  • 問題:sサイズの重複文を実行する必要があります.
  • 例)今回の問題