Submission #1174479

---

Source Code Expand

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 日本橋ハーフマラソン 2017/03/04 B
 *
 * @author tsukammo
 */
public class Main {

	// B
	public static void main(String[] args) {
		new Main().play();
	}

	private void play() {
		Scanner in = new Scanner(System.in);
		input(in);
		solve();
	}

	private void solve() {

		for (turn = 0; turn < 300; turn++) {
			StringBuffer output = new StringBuffer();
			init();
			for (int i = 0; i < K; i++) {
				String move = move(cars[i]);
				output.append(move);
			}
			out.add(output.toString());
		}

		System.out.println(out.size());
		for (String s : out) {
			System.out.println(s);
		}
	}

	private String move(Car car) {
		int ans = -1;
		if (!car.finish && !car.stop && (car.goTar || car.escape)) {
			for (int i = 0; i < dx.length; i++) {
				int nx = car.x + dx[i];
				int ny = car.y + dy[i];
				if (inField(nx, ny) && field[ny][nx] == 0) {
					if (car.goTar) { // 目的値になるべく近づく
						int[][] dist = calcMoveTar(car);
						if (dist[car.y][car.x] > dist[ny][nx]) {
							field[ny][nx] = 1;
							car.x = nx;
							car.y = ny;
							return order[i];
						}
					} else if (car.escape) { // なるべく邪魔にならないところに移動
						if (calcCenterDist(car.x, car.y) < calcCenterDist(nx, ny)) {
							field[ny][nx] = 1;
							car.x = nx;
							car.y = ny;
							return order[i];
						}
					}
					if (rnd.nextInt(10) < 8) {
						ans = i;
					}
				}
			}
		}
		if (ans == -1) {
			field[car.y][car.x] = 2; // 動く気がない
		} else {
			int nx = car.x + dx[ans];
			int ny = car.y + dy[ans];
			field[ny][nx] = 1;
			car.x = nx;
			car.y = ny;
			return order[ans];
		}
		return "-";
	}

	private int[][] calcMoveTar(Car car) {
		boolean[][] checked = new boolean[H][W];
		Queue<int[]> list = new ArrayDeque<int[]>();
		// 目的地から逆算する
		list.add(new int[] { car.tarX, car.tarY });
		int[][] dist = new int[H][W];
		dist[car.tarY][car.tarX] = 1;
		while (list.size() > 0) {
			int[] now = list.poll();
			int x = now[0];
			int y = now[1];
			for (int k = 0; k < dx.length; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (inField(nx, ny) && field[ny][nx] < 2) {
					if ((dist[ny][nx] == 0 || dist[ny][nx] > dist[y][x] + 1)) {
						list.add(new int[] { nx, ny });
						dist[ny][nx] = dist[y][x] + 1;
						checked[ny][nx] = true;
					}
				} else if (inField(nx, ny)) {// どうやってもいけない場合できるだけ近くへ。
					if ((dist[ny][nx] == 0 || dist[ny][nx] > dist[y][x] + 100)) {
						list.add(new int[] { nx, ny });
						dist[ny][nx] = dist[y][x] + 100;
						checked[ny][nx] = true;
					}
				}

			}
		}
		return dist;
	}

	private void init() {
		field = new int[H][W];
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				field[i][j] = 0;
			}
		}
		for (Car car : cars) {
			field[car.y][car.x] = 1;
			car.stop = false;
			int val = Math.abs(car.tarX - W / 2) + Math.abs(car.tarY - H / 2);
			if (car.x == car.tarX && car.y == car.tarY) {
				car.finish = true;
			} else if (checkStop(car)) {
				car.stop = true;
			} else if (val < turn / 20 + 1) {
				car.goTar = true;
			} else if (val > 30 - (turn / 5 + 3)) {
				car.escape = true;
			} else {
				car.stop = true;
			}
			if (car.finish || car.stop) {
				field[car.y][car.x] = 2; // 動く気がない
			}

		}
	}

	private boolean checkStop(Car car) {
		for (int i = 0; i < dx.length; i++) {
			int nx = car.x + dx[i];
			int ny = car.y + dy[i];
			if (inField(nx, ny) && field[ny][nx] == 0) {
				return false;
			}
		}
		return true;
	}

	private int calcCenterDist(int x, int y) {
		return Math.abs(x - W / 2) + Math.abs(y - H / 2);
	}

	static final int[] dx = new int[] { 1, 0, -1, 0 };
	static final int[] dy = new int[] { 0, 1, 0, -1 };
	static final String[] order = new String[] { "R", "D", "L", "U" };
	// static final char[] order = new char[] { 'D', 'R', 'U', 'L' };

	private boolean inField(int ni, int nj) {
		return (ni > -1 && ni < W && nj > -1 && nj < H);
	}

	private void input(Scanner in) {
		H = in.nextInt(); // Y
		W = in.nextInt(); // X
		K = in.nextInt();
		T = in.nextInt();
		System.err.println(H + " " + W + " " + K + " " + T);
		in.nextLine();
		cars = new Car[K];
		for (int i = 0; i < K; i++) {
			String[] tmp = in.nextLine().split(" ");
			cars[i] = new Car(Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1]), Integer.parseInt(tmp[2]),
					Integer.parseInt(tmp[3]));
		}
		System.err.println("input OK");
	}

	int H;
	int W;
	int K;
	int T;
	int turn;
	int[][] field;
	ArrayList<String> out = new ArrayList<>();
	Car[] cars;
	Random rnd = new Random(19881221L);

	class Car {
		int x;
		int y;
		int tarX;
		int tarY;
		boolean stop = false;
		boolean goTar = false;
		boolean escape = false;
		boolean finish = false;

		Car(int ri, int ci, int si, int di) {// 逆順
			y = ri - 1;
			x = ci - 1;
			tarY = si - 1;
			tarX = di - 1;
		}
	}

	class Random {
		private long seed;
		private final long multiplier = 0x5DEECE66DL, addend = 0xBL, mask = (1L << 48) - 1;

		Random(long seed) {
			this.seed = seed;
		}

		int nextInt(int n) {
			if (n <= 1)
				return 0;
			if ((n & -n) == n) {
				return (int) ((n * (long) ((int) ((seed = (seed * multiplier + addend) & mask) >>> 17))) >> 31);
			}
			int bits, val;
			do {
				bits = (int) ((seed = (seed * multiplier + addend) & mask) >>> 17);
				val = bits % n;
			} while (bits - val + (n - 1) < 0);
			return val;
		}

		double nextDouble() {
			return nextInt(10000000) / 10000000.0;
		}
	}
}

Submission Info

Judge Result