Indeedなう（予選A）D: 15パズル（幅優先探索・枝刈り）

問題

D: パズル - Indeedなう（予選A） | AtCoder

解法

あるマス(i, j)の数字が本来あるべきマスとのマンハッタン距離を計算する。本来あるべきマスまで移動するのに最低でもマンハッタン距離分だけの手数がかかるので、他の数字についてもマンハッタン距離を出して足し合わせ、24手を超えたら弾けば良い。

コード

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
	private static int H;
	private static int W;
	private static final int[][] dr = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

	public static void main(String[] args) {
		H = nextInt();
		W = nextInt();
		int[][] puzzle = new int[H][W];
		for (int i = 0; i < puzzle.length; i++) {
			for (int j = 0; j < puzzle[i].length; j++) {
				puzzle[i][j] = nextInt();
			}
		}

		Deque<PuzzleMap> deque = new ArrayDeque<>();
		deque.add(new PuzzleMap(puzzle, 0, -10));
		while (!deque.isEmpty()) {
			PuzzleMap map = deque.pollFirst();
			if (check(map.pmap)) {
				System.out.println(map.t);
				return;
			}

			int ni = -1;
			int nj = -1;
			seek: for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if (map.pmap[i][j] == 0) {
						ni = i;
						nj = j;
						break seek;
					}
				}
			}

			for (int d = 0; d < dr.length; d++) {
				/*
				 * map.d=0ならd=1はダメ
				 */
				if (map.d + d == 1 || map.d + d == 5) {
					continue;
				}

				int x = ni + dr[d][0];
				int y = nj + dr[d][1];
				if (x >= 0 && x < H && y >= 0 && y < W) {
					int[][] putmap = new int[H][W];
					for (int i = 0; i < H; i++) {
						for (int j = 0; j < W; j++) {
							putmap[i][j] = map.pmap[i][j];
						}
					}
					putmap[ni][nj] = putmap[x][y];
					putmap[x][y] = 0;

					int LD = 0;
					for (int i = 0; i < putmap.length; i++) {
						for (int j = 0; j < putmap[i].length; j++) {
							if (putmap[i][j] == 0) {
								continue;
							}
							int num = putmap[i][j];
							int ai = (num - 1) / W;
							int aj = (num - 1) % W;
							LD += Math.abs(i - ai) + Math.abs(j - aj);
						}
					}
					if (map.t + 1 + LD <= 24) {
						deque.addLast(new PuzzleMap(putmap, map.t + 1, d));
					}
				}
			}

		}

	}

	static boolean check(int[][] p) {
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p[i].length; j++) {
				if (p[i][j] != (W * i + j + 1) % (H * W)) {
					return false;
				}
			}
		}
		return true;

	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

}

class PuzzleMap {
	int[][] pmap;
	int t;// t手目
	int d;// 前に動かした方向

	public PuzzleMap(int[][] puzzle, int t, int d) {
		this.pmap = new int[puzzle.length][puzzle[0].length];
		for (int i = 0; i < puzzle.length; i++) {
			for (int j = 0; j < puzzle[i].length; j++) {
				this.pmap[i][j] = puzzle[i][j];
			}
		}
		this.t = t;
		this.d = d;
	}

}