[BOJ 2873]ジェットコースター

完全に探求できない理由?

この問題の最大行と列は1000であり,2次元配列の1つの要素から最大4つの方向に進むことができる.アクセス配列を除外しても(N-@)^1000*1000はTLEを生成します.

一番嬉しい累積値は?

できるだけ多くの要素にアクセスすればいいです.では、全スキャンですべてのノードが表示されますか?自分で例題を作って,問題を観察する.

動作が奇数または奇数の場合

上の図に示すように、すべての要素に配列内の数値の順にアクセスできます.

行と列が偶数の場合

自分で例を作ってみれば、行も列も偶数のときに問題が発生することがわかります.

上の図に示すように、順番にスキャンすると、次の最後の行はアクセス禁止になります.

パスを変更して次の最後の行にアクセスしたらどうですか?

最後の行も訪問するなら、ある瞬間に1行下がるのではなく、2行下がる.

要素にアクセスしないとどうなりますか?

上の2つの図から、要素にアクセスせずに2つのローに同時にアクセスすると、最後のローまでパスの順序が変更されると推測できます.

要素を指定するにはどうすればいいですか?

任意の行で発生できますが、任意の列には適用されません.偶数行は奇数列のみ、奇数行は偶数列のみです.
パスを描くと、直感的な感じがします.条件を満たす最小数を除いて、アクセスできます.

コードの実装方法

アクセスされていない要素を持つ行または近い行を除き、上から右にスキャンします.
出発地と目的地の行・列情報を利用して探索区間を縮小し,アクセス順に行う.

JAVAコード

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb;
	static StringBuilder rsb;

	static int[][] map;
	static int R, C;
	
	public static void main (String[] args) throws java.lang.Exception
	{
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder("");
		rsb = new StringBuilder("");
		
		String[] sArr;
		sArr = br.readLine().split(" ");
		R = Integer.valueOf(sArr[0]);
		C = Integer.valueOf(sArr[1]);
		
		map = new int[R][C];

		for(int i = 0; i < R; i++){
			sArr = br.readLine().split(" ");
			for(int j = 0; j < sArr.length; j++){
				map[i][j] = Integer.valueOf(sArr[j]);
			}
		}
		
		if(R % 2 == 1){
			for(int i = 0; i < R; i++){
				if(i % 2 == 0){
					for(int j = 0; j < C - 1; j++) sb.append("R");
				}else{
					for(int j = 0; j < C - 1; j++) sb.append("L");
				}
				
				if(i != R - 1)
					sb.append("D");
			}
			
			bw.write(sb.toString() + "\n");
			bw.flush();
		}else if(C % 2 == 1){
			for(int i = 0; i < C; i++){
				if(i % 2 == 0){
					for(int j = 0; j < R - 1; j++) sb.append("D");
				}else{
					for(int j = 0; j < R - 1; j++) sb.append("U");
				}
				
				if(i != C - 1)
					sb.append("R");
			}
			
			bw.write(sb.toString() + "\n");
			bw.flush();
		}else{
			int mr = -1, mc = -1;
			int val = Integer.MAX_VALUE;
			for(int i = 0; i < R; i++){
				if(i % 2 == 0){
					for(int j = 1; j < C; j += 2){
						if(map[i][j] < val){
							val = map[i][j]; mr = i; mc = j;
						}
					}
				}else{
					for(int j = 0; j < C; j += 2){
						if(map[i][j] < val){
							val = map[i][j]; mr = i; mc = j;
						}
					}
				}
			}
			
			int r1 = 0, c1 = 0, r2 = R - 1, c2 = C - 1;
			while(r2 - r1 > 1){
				if(mr - r1 > 1){
					for(int j = 0; j < C - 1; j++) sb.append("R");
					sb.append("D");
					for(int j = 0; j < C - 1; j++) sb.append("L");
					sb.append("D");
					
					r1 += 2;
				}
				
				if(r2 - mr > 1){
					for(int j = 0; j < C - 1; j++) rsb.append("R");
					rsb.append("D");
					for(int j = 0; j < C - 1; j++) rsb.append("L");
					rsb.append("D");

					r2 -= 2;
				}
			}
			
			while(c2 - c1 > 1){
				if(mc - c1 > 1){
					sb.append("D");
					sb.append("R");
					sb.append("U");
					sb.append("R");
					
					c1 += 2;
				}
				
				if(c2 - mc > 1){
					rsb.append("D");
					rsb.append("R");
					rsb.append("U");
					rsb.append("R");
					
					c2 -= 2;
				}
			}
			
			if(r1 + 1 == mr){
				sb.append("R");
				sb.append("D");
			}else if(r2 - 1 == mr){
				sb.append("D");
				sb.append("R");
			}
			
			sb.append(rsb.reverse());
			bw.write(sb.toString() + "\n");
			bw.flush();
		}
	}
}