（部分点解法）壁抜け [AtCoder Beginner Contest 020 C]

atcoder.jp

前回の記事にあるプログラムを使って解いています。

jpliterature.hatenablog.com

入力・出力部分

static int h, w;
static Point s, g;
static char[][] map;
static int x;
static ArrayList<Integer> list = new ArrayList<>();

void solve () {

	//入力
	h = nextInt();
	w = nextInt();
	if (h>3 || w>3) { //部分点以外の入力が来たら終了させる
		out.println("TLE");
		return;
	}
	int t = nextInt();
	map = new char[h][w];
	for (int i=0; i<h; i++) {
		map[i] = next().toCharArray();
		for (int j=0; j<w; j++) {
			if (map[i][j] == 'S') s = new Point(j, i);
			else if (map[i][j] == 'G') g = new Point(j, i);
		}
	}
	int[][] b = new int[h][w];
	for (int i=0; i<h; i++) Arrays.fill(b[i], -1);


	//再帰関数
	for (x=t-1; x>=1; x--) {
		list.clear();
		rec (s, b, 0);
		for (int i=0; i<list.size(); i++) {
			if (list.get(i) <= t) {
				out.println(x);
				return;
			}
		}
	}

}

処理の流れは以下のようになっています。

・forループで x の値を順番に t-1 から 1 まで回す
・再帰関数を用いて、ある x におけるマス目上の全経路を探索し、各経路のゴールまでの歩数をリストに詰める
・リストの中に歩数 t 以下のものが初めて出現した時点で x を出力して終了

※追記：リストに詰めずとも、再帰中に出現した時点で x を出力して終了すればいいですね

再帰関数部分

static void rec (Point p, int[][] memo, int n) {

	//終了条件
	if (p.getX()<0 || p.getY()<0 || p.getX()>w-1 || p.getY()>h-1) {
		return;
	}
	if (memo[p.getY()][p.getX()]>=0 && !p.equals(s)) {
		return;
	}
	if (p.getX()==g.getX() && p.getY()==g.getY()) {
		//ゴールに到達したなら、歩数をリストに返す
		list.add(n);
		return;
	}

	//訪問地点メモ用配列のディープコピー
	int[][] b = new int[h][w];
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			b[i][j] = memo[i][j];
		}
	}

	//現在地点が"#"なら、x-1を余計に歩数に加算する
	if (map[p.getY()][p.getX()] == '#') {
		n += x - 1;
		b[p.getY()][p.getX()] = n;
	}
	else b[p.getY()][p.getX()] = n;

	//四方へ伸ばす
	rec(new Point(p.getX(), p.getY()-1), b, n+1);
	rec(new Point(p.getX(), p.getY()+1), b, n+1);
	rec(new Point(p.getX()-1, p.getY()), b, n+1);
	rec(new Point(p.getX()+1, p.getY()), b, n+1);

}

満点解法はダイクストラ法（？）とかいうアルゴリズムを使わないといけないみたいです。
ひとまず、身の丈にあったプログラムを書いて部分点は貰えたので、満足してます。