AOJ2223 Kaeru Jump

問題リンク Kaeru Jump

• 概要

H*Wの大きさの池に葉っぱと1匹のカエルがいる。カエルは上下左右へ飛ぶ方向を決めたら、その方向の一番近い葉っぱに飛ぶ。このとき、飛ぶ前に乗っていた葉っぱは消えてなくなる。また、カエルは自分が向いている方向の真反対の方向へは飛べない。カエルの初期位置と初期方向が与えられたとき、池の葉っぱ全てに乗れるような動き方を出力せよ。
1 <= H, W <= 10
葉っぱの数は高々30
答えとなる動き方はユニークに存在する

• 解法

飛ぶ方向は常に3方向あるので、単純に見積もって3^30通りの動き方があり、工夫をしないと計算量が爆発してしまう。っと思うかもしれませんが、実は凝った枝刈りが無くても普通の探索を書くだけで間に合います。
枝刈りについて余談を少し。
4方向について飛び先がない葉っぱが1つでもあったら、その葉っぱへ到達不可能になるのでその動き方は既に破綻していることになります(葉っぱが残り2枚のときは例外です)。さらに、そのような孤独な葉っぱは、カエルの乗っている葉っぱの最近隣のものに起こりえます。よって、現在位置の葉っぱを取り除き、最近隣の4つの葉っぱについて孤独になっていないかチェックし、そのようなものが1つ以上あったら枝刈りをする方法が使えます。
枝刈り前は150msecで終わり、枝刈りすると110msecになります。どう考えても実装時間の無駄です。本当にありがとうございました。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Kaeru Jump
public class AOJ2223 {

	int h, w, n;
	char[][] m;
	int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
	char[] str = {'U','R','D','L'};
	char[] res;

	int[][] near(int i, int j){
		int[][] r = new int[4][2];
		for(int[]a:r)Arrays.fill(a, -1);
		for(int k=0;k<4;k++){
			int pi = i+d[k][0], pj = j+d[k][1];
			while(0<=pi&&pi<h&&0<=pj&&pj<w){
				if(m[pi][pj]=='o'){
					r[k][0] = pi; r[k][1] = pj; break;
				}
				pi += d[k][0]; pj += d[k][1];
			}
		}
		return r;
	}

	boolean dfs(int i, int j, int D, int c){
		if(c==n-1)return true;
		int[][] e = near(i, j);
		for(int k=0;k<4;k++){
			if(e[k][0]==-1||D==(k+2)%4)continue;
			res[c] = str[k];
			m[i][j] = '.';
			if(dfs(e[k][0], e[k][1], k, c+1))return true;
			m[i][j] = 'o';
		}
		return false;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		h = sc.nextInt(); w = sc.nextInt();
		n = 0;
		m = new char[h][];
		int si = -1, sj = -1, sd = -1;
		for(int i=0;i<h;i++){
			m[i] = sc.next().toCharArray();
			for(int j=0;j<w;j++){
				if(m[i][j]=='.')continue;
				n++;
				if(m[i][j]=='o')continue;
				si = i; sj = j;
				sd = m[i][j]=='U'?0:m[i][j]=='R'?1:m[i][j]=='D'?2:3;
				m[i][j] = 'o';
			}
		}
		res = new char[n-1];
		dfs(si, sj, sd, 0);
		System.out.println(new String(res));
	}

	public static void main(String[] args) {
		new AOJ2223().run();
	}
}