Submission #671064

---

Source Code Expand

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

public class Main {
	final static int row = 30;
	final static int col = 30;
	static int[][] map = new int[row][col];
	static int[][] map0 = new int[row][col];
	static int[][] map1 = new int[row][col];
	static int[][] map2 = new int[row][col];
	static int[][] map3 = new int[row][col];
	final static int[] dx = new int[] { 1, 0, 0, -1 };
	final static int[] dy = new int[] { 0, 1, -1, 0 };
	final static int[] dx1 = new int[] { -1, 0, 0, 1 };
	final static int[] dy1 = new int[] { 0, -1, 1, 0 };
	final static int[] dx2 = new int[] { 1, 0, 0, -1 };
	final static int[] dy2 = new int[] { 0, 1, -1, 0 };
	final static int[] dx3 = new int[] { 0, -1, 1, 0 };
	final static int[] dy3 = new int[] { 1, 0, 0, -1 };
	final static int[] dx4 = new int[] { 0, 1, -1, 0 };
	final static int[] dy4 = new int[] { -1, 0, 0, 1 };
	final static int cout = 1;
	int turn = 1;
	int turns[] = { 1, 1, 1, 1 };
	Queue<int[]> q0 = new ArrayDeque<int[]>();
	Queue<int[]> q1 = new ArrayDeque<int[]>();
	Queue<int[]> q2 = new ArrayDeque<int[]>();
	Queue<int[]> q3 = new ArrayDeque<int[]>();

	public static void main(String[] args) {

		Main m = new Main();
		m.input();
		for (int i = 0; i < 4; i++) {
			m.solve(i);
		}
		m.output();
		// System.out.flush();
		// System.out.println("手数_" + turn);
	}

	private void output() {
		int id = 0;
		int min = turns[0];
		for (int i = 0; i < turns.length; i++) {
//			System.out.println(i + "番目手数_" + turns[i]);
			if (turns[i] < min) {
				id = i;
				min = turns[i];
			}
		}
		// System.err.println("id_" + id);
		if (id == 0) {
			outputOrder(q0);
		}
		if (id == 1) {
			outputOrder(q1);
		}
		if (id == 2) {
			outputOrder(q2);
		}
		if (id == 3) {
			outputOrder(q3);
		}
	}

	private void outputOrder(Queue<int[]> q) {
		for (int[] e : q) {
			 System.out.println((e[0] + 1) + " " + (e[1] + 1));
		}
	}

	public void solve(int n) {
		while (true) {
			int[] p = choiceATop(n);
			if (p == null) {
				break;
			} else {
				ArrayList<int[]> list = new ArrayList<int[]>();
				list.add(p);
				while (list.size() > 0) {
					int[] tmp = list.get(list.size() - 1);
					int[] vec = whitchGo(list, n, tmp[0], tmp[1]);
					if (vec == null) {
						break;
					}
					list.add(vec);
				}
				outputStock(n, list);
			}
		}
	}

	public void simu(int n,int[] p, int[][] m) {
		copyMap(m, map);
		ArrayList<int[]> list = new ArrayList<int[]>();
		list.add(p);
		while (list.size() > 0) {
			int[] tmp = list.get(list.size() - 1);
			int[] vec = whitchGo(list, n, tmp[0], tmp[1]);
			if (vec == null) {
				break;
			}
			list.add(vec);
		}
		outputStock(-1, list);
	}

	int createPath(int n, int[] s) {
		int c = 0;
		int[] vec = new int[2];
		vec[0] = s[0];
		vec[1] = s[1];
		ArrayList<int[]> list = new ArrayList<int[]>();
		while (true) {
			vec = whitchGo(list, n, vec[0], vec[1]);
			if (vec == null) {
				break;
			}
			c++;
		}
		return c;
	}

	private void outputStock(int n, ArrayList<int[]> list) {
		for (int[] e : list) {
			int r = e[0];
			int c = e[1];

			if (n == 0) {
				q0.add(e);
				map0[r][c] -= 1;
			}
			if (n == 1) {
				q1.add(e);
				map1[r][c] -= 1;
			}
			if (n == 2) {
				q2.add(e);
				map2[r][c] -= 1;
			}
			if (n == 3) {
				q3.add(e);
				map3[r][c] -= 1;
			}
			if (n == -1) {
				map[r][c] -= 1;
			}
		}
		// System.err.println("turn_" + turns[n]);
		if (n > -1)
			turns[n]++;
		// for (int i = 0; i < row; i++) {
		// for (int j = 0; j < col; j++) {
		// System.err.print(map[i][j] + " ");
		// }
		// System.err.println();
		//
		// }
	}

	public void input() {

		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				int tmp = sc.nextInt();
				map[i][j] = tmp;
				map0[i][j] = tmp;
				map1[i][j] = tmp;
				map2[i][j] = tmp;
				map3[i][j] = tmp;
			}
		}
	}

	void copyMap(int[][] moto, int[][] saki) {
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				saki[i][j] = moto[i][j];
			}
		}
	}

	int countTop(int[][] map) {
		int ans = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				int v = map[i][j];
				if (v != 0) {
					boolean top = true;
					for (int k = 0; k < dx.length; k++) {
						int nr = i + dx[k];
						int nc = j + dy[k];
						if (inStage(nr, nc) && map[nr][nc] > v) {
							top = false;
							break;
						}
					}
					if (top)
						ans++;
				}
			}
		}
		return ans;
	}

	int[] choiceATop(int n) {
		int tryc = 0;
		int tr = -1, tc = -1;
		int min = 0;
		int[] ans1 = new int[] { -1, -1 };
		int list = -1;
		if (n == 0)
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					if (tryc < cout && isTop(n, i, j)) {
						tryc++;
						int[] tmp = { i, j };
						if (tryc == 1 || list < createPath(n, tmp)) {
							ans1[0] = i;
							ans1[1] = j;
							list = createPath(n, ans1);
						}
					} else if (isTop(n, i, j)) {
						int[] ans = { i, j };
						simu(n,ans1, map1);
						int topCountB = countTop(map);
						simu(n,ans, map1);
						int topCountA = countTop(map);
						if (topCountB > topCountA) {
							return ans1;
						}
						if (list != Integer.MAX_VALUE && list >= createPath(n, ans)) {
							return ans1;
						}
						return ans;
					}
					if (i == row - 1 && j == col - 1) {
						if (ans1[0] == -1) {
							return null;
						}
						return ans1;
					}
				}
			}
		if (n == 1)
			for (int i = row - 1; i > -1; i--) {
				for (int j = col - 1; j > -1; j--) {
					if (tryc < cout && isTop(n, i, j)) {
						tryc++;
						int[] tmp = { i, j };
						if (tryc == 1 || list < createPath(n, tmp)) {
							ans1[0] = i;
							ans1[1] = j;
							list = createPath(n, ans1);
						}
						if (ans1[0] != -1) {
						}
					} else if (isTop(n, i, j)) {
						int[] ans = { i, j };
						simu(n,ans1, map1);
						int topCountB = countTop(map);
						simu(n,ans, map1);
						int topCountA = countTop(map);
						if (topCountB > topCountA) {
							return ans1;
						}
						if (list >= createPath(n, ans)) {
							return ans1;
						}
						return ans;
					}
					if (i == 0 && j == 0) {
						if (ans1[0] == -1) {
							return null;
						}
						return ans1;
					}
				}
			}
		if (n == 2)
			for (int j = col - 1; j > -1; j--) {
				for (int i = 0; i < row; i++) {
					if (tryc < cout && isTop(n, i, j)) {
						tryc++;
						int[] tmp = { i, j };
						if (tryc == 1 || list < createPath(n, tmp)) {
							ans1[0] = i;
							ans1[1] = j;
							list = createPath(n, ans1);
						}
					} else if (isTop(n, i, j)) {
						int[] ans = { i, j };
						simu(n,ans1, map1);
						int topCountB = countTop(map);
						simu(n,ans, map1);
						int topCountA = countTop(map);
						if (topCountB > topCountA) {
							return ans1;
						}
						if (tryc == 1 || list >= createPath(n, ans)) {
							return ans1;
						}
						return ans;
					}
					if (i == row - 1 && j == 0) {
						if (ans1[0] == -1) {
							return null;
						}
						return ans1;
					}
				}
			}
		if (n == 3)
			for (int j = 0; j < col; j++) {
				for (int i = row - 1; i > -1; i--) {
					if (tryc < cout && isTop(n, i, j)) {
						tryc++;
						int[] tmp = { i, j };
						if (list < createPath(n, tmp)) {
							ans1[0] = i;
							ans1[1] = j;
							list = createPath(n, ans1);
						}
					} else if (isTop(n, i, j)) {
						int[] ans = { i, j };
						simu(n,ans1, map1);
						int topCountB = countTop(map);
						simu(n,ans, map1);
						int topCountA = countTop(map);
						if (topCountB > topCountA) {
							return ans1;
						}
						if (list >= createPath(n, ans)) {
							return ans1;
						}
						return ans;
					}
					if (i == 0 && j == col - 1) {
						if (ans1[0] == -1) {
							return null;
						}
						return ans1;
					}
				}
			}
		return null;
	}

	// 近傍最上点かどうか。同立も含む。
	boolean isTop(int n, int r, int c) {
		int v = getMapValue(n, r, c);

		if (v == 0) {
			return false;
		}
		for (int i = 0; i < dx.length; i++) {
			int nr = r + dx[i];
			int nc = c + dy[i];
			if (inStage(nr, nc) && getMapValue(n, nr, nc) > v) {
				return false;
			}
		}
		return true;
	}

	boolean isSameTop(int n, int r, int c) {
		int v = getMapValue(n, r, c);

		if (v == 0) {
			return false;
		}
		for (int i = 0; i < dx.length; i++) {
			int nr = r + dx[i];
			int nc = c + dy[i];
			if (inStage(nr, nc) && getMapValue(n, nr, nc) >= v) {
				return false;
			}
		}
		return true;
	}

	int getMapValue(int n, int r, int c) {
		if (n == 0)
			return map0[r][c];
		if (n == 1)
			return map1[r][c];
		if (n == 2)
			return map2[r][c];
		if (n == 3)
			return map3[r][c];

		return -1;
	}

	boolean hasNext(int n, int r, int c) {
		int v = getMapValue(n, r, c);
		for (int i = 0; i < dx.length; i++) {
			int nr = r + dx[i];
			int nc = c + dy[i];
			if (inStage(nr, nc) && v - 1 != 0 && v - 1 == getMapValue(n, nr, nc)) {
				return true;
			}
		}
		return false;
	}

	boolean sameMath(int n, ArrayList<int[]> list, int[] p) {
		for (int[] e : list) {
			for (int i = 0; i < p.length; i++) {
				if (p[i] != e[i]) {
					break;
				}
				if (i == p.length - 1) {
					return true;
				}
			}
		}
		return false;
	}

	// 移動すべき方向をひとつきめる
	int[] whitchGo(ArrayList<int[]> list, int n, int r, int c) {
		int lg = 0;
		if (n == 0)
			return whitchGoCalc(list, n, r, c, dx1, dy1);
		if (n == 1)
			return whitchGoCalc(list, n, r, c, dx2, dy2);
		if (n == 2)
			return whitchGoCalc(list, n, r, c, dx3, dy3);
		if (n == 3)
			return whitchGoCalc(list, n, r, c, dx4, dy4);
		return null;
	}

	int[] whitchGoCalc(ArrayList<int[]> list, int n, int r, int c, int[] dx0, int[] dy0) {
		int v = getMapValue(n, r, c);
		int tr = -1, tc = -1;
		boolean go4 = false;
		for (int i = 0; i < dx0.length; i++) {
			int nr = r + dx0[i];
			int nc = c + dy0[i];
			if (inStage(nr, nc) && v - 1 != 0 && v - 1 == getMapValue(n, nr, nc)) {
				if (i == 3) {
					if (n > 1 && nr < row - 1 && nr > 1) {
						int[] tmpR = new int[] { nr + 1, nc };
						int[] tmpL = new int[] { nr - 1, nc };
						if (sameMath(n, list, tmpR) || sameMath(n, list, tmpL)) {
							go4 = true;
						}
					}
					if (n < 2 && nc < col - 1 && nc > 1) {
						int[] tmpR = new int[] { nr, nc + 1 };
						int[] tmpL = new int[] { nr, nc - 1 };
						if (sameMath(n, list, tmpR) || sameMath(n, list, tmpL)) {
							go4 = true;
						}
					}
				}
				if ((i < 3 || go4) && tr == -1) {
					tr = nr;
					tc = nc;
				} else {
					// 元のがそばに同値以上がなくて、新しい方がある時
					if (i < 3 && !nearSame(n, tr, tc) && nearSame(n, nr, nc)) {
						tr = nr;
						tc = nc;
					}
				}
			}
			if (i == dx0.length - 1 && tr != -1) {
				int[] ans = { tr, tc };
				return ans;
			}
		}
		return null;
	}

	boolean inStage(int nr, int nc) {
		if (nr > -1 && nc > -1 && nr < row && nc < col)
			return true;
		return false;
	}

	boolean nearSame(int n, int r, int c) {
		int v = getMapValue(n, r, c);
		for (int i = 0; i < dx.length; i++) {
			int nr = r + dx[i];
			int nc = c + dy[i];
			if (inStage(nr, nc) && v > getMapValue(n, nr, nc)) {
				return true;
			}
		}

		return false;
	}

	boolean nearSameE(int n, int r, int c) {
		int v = getMapValue(n, r, c);
		for (int i = 0; i < dx.length; i++) {
			int nr = r + dx[i];
			int nc = c + dy[i];
			if (inStage(nr, nc) && v >= getMapValue(n, nr, nc)) {
				return true;
			}
		}

		return false;
	}
}

Submission Info

Judge Result