Submission #670969

---

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 };
	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);
			}
		}
	}

	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;
			}
		}
		// System.err.println("turn_" + turns[n]);
		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;
			}
		}
	}

	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 (ans1[0]==-1&&isTop(n, i, j)) {
						ans1[0] = i;
						ans1[1] = j;
						list = createPath(n, ans1);
					}else if (isTop(n,i,j)){
						int[] ans = { i, j };
						if(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 (ans1[0]==-1&&isTop(n, i, j)) {
						ans1[0] = i;
						ans1[1] = j;
						list = createPath(n, ans1);
					}else if (isTop(n,i,j)){
						int[] ans = { i, j };
						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 (ans1[0]==-1&&isTop(n, i, j)) {
						ans1[0] = i;
						ans1[1] = j;
						list = createPath(n, ans1);
					}else if (isTop(n,i,j)){
						int[] ans = { i, j };
						if(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 (ans1[0]==-1&&isTop(n, i, j)) {
						ans1[0] = i;
						ans1[1] = j;
						list = createPath(n, ans1);
					}else if (isTop(n,i,j)){
						int[] ans = { i, j };
						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(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 v = getMapValue(n, r, c);
		int tr = -1, tc = -1;
		if (n == 0)
			for (int i = 0; i < dx1.length; i++) {
				int nr = r + dx1[i];
				int nc = c + dy1[i];
				if (inStage(nr, nc) && v - 1 != 0 && v - 1 == getMapValue(n, nr, nc)) {
					boolean go4 = false;
					if (i == 3 && nc < col - 1 && nc > 1) {
						int[] tmpR = new int[] { nr, nc + 1 };
						int[] tmpL = new int[] { nr, nc - 1 };
						if (sameMath(list, tmpR) || sameMath(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 == dx1.length - 1 && tr != -1) {
					int[] ans = { tr, tc };
					return ans;
				}
			}
		if (n == 1)
			for (int i = 0; i < dx2.length; i++) {
				int nr = r + dx2[i];
				int nc = c + dy2[i];
				if (inStage(nr, nc) && v - 1 != 0 && v - 1 == getMapValue(n, nr, nc)) {
					boolean go4 = false;
					if (i == 3 && nc < col - 1 && nc > 1) {
						int[] tmpR = new int[] { nr, nc + 1 };
						int[] tmpL = new int[] { nr, nc - 1 };
						if (sameMath(list, tmpR) || sameMath(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 == dx1.length - 1 && tr != -1) {
					int[] ans = { tr, tc };
					return ans;
				}
			}
		if (n == 2)
			for (int i = 0; i < dx3.length; i++) {
				int nr = r + dx3[i];
				int nc = c + dy3[i];
				if (inStage(nr, nc) && v - 1 != 0 && v - 1 == getMapValue(n, nr, nc)) {
					boolean go4 = false;
					if (i == 3 && nr < row - 1 && nr > 1) {
						int[] tmpR = new int[] { nr + 1, nc };
						int[] tmpL = new int[] { nr - 1, nc };
						if (sameMath(list, tmpR) || sameMath(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 == dx1.length - 1 && tr != -1) {
					int[] ans = { tr, tc };
					return ans;
				}
			}
		if (n == 3)
			for (int i = 0; i < dx4.length; i++) {
				int nr = r + dx4[i];
				int nc = c + dy4[i];
				if (inStage(nr, nc) && v - 1 != 0 && v - 1 == getMapValue(n, nr, nc)) {
					boolean go4 = false;
					if (i == 3 && nr < row - 1 && nr > 1) {
						int[] tmpR = new int[] { nr + 1, nc };
						int[] tmpL = new int[] { nr - 1, nc };
						if (sameMath(list, tmpR) || sameMath(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 == dx1.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;
	}
}

Submission Info

Judge Result