最近は大学の課題に押しつぶされている事に加え、今やっている問題も自分があまり慣れていない領域なのでなかなか投稿し辛いのですが、頑張りますよ〜
サーっと書いてみたのですが、はたからみてもサーっと書いた様な幅優先探索のコードになってしまいました。答えが初期値から書き変わらないし・・・
この後は、また最初から全探索を解いて行こうと思います(出来てないしなぁ・・・ あと、まだ1問あるのでそれ解いてから最初に戻る感じになります)出来る様になりたいし、周りの人が頭良い分、自分は努力で埋めるしか無いし・・・
問題元:SRM453.5 Div2 Level2
問題文:
最近、迷路名人のマイクは、裏庭に巨大迷路を作りました。迷路のi行目i列の文字は、低木があって取れない場合は'X'、通れる場合は'.'となります。マイクは、彼の友人である跳躍名人のジムに、その迷路を解かせたいと思っています。ジムはstartCol行startRow列から開始します。
ジムは、一般的な解き方とは違って、迷路を単に歩くのではなく、飛んで移動出来ます。ジムがとれる動きは、moveRowとmoveColに記されています。i番目の要素はジムが取りうる動きに対応しており、現在の列、行はそれぞれmoveRor[i]、moveCol[i]で変更されます。たとえば、
moveRow = {1, 0, -1}
moveCol = {3, -2, 5}
の場合、ジムの取りうる動きは
(1, 3),(0, -2),(-1, 5)となります。
ただし、ジムは迷路の外に移動する事は出来ず、通過出来ない低木の上に動く事も出来ません。
マイクはジムが迷路から出られない様にしたいと思っています。そして、マイクは、迷路内のどの'.'にも出口を置く事が出来ます。もし、出られない様にする事が不可能なら、出来るだけジムの移動距離が長くなる様にしようと思っています。賢いジムは、常に最小の跳躍数で迷路を抜け出します。ジムが迷路から抜け出すときの最大跳躍数を返してください。もし抜け出せないときは−1を返してください。
import java.util.*;
public class Mazemaker {
int longestPath(String[] maze, int startRow, int startCol, int[] moveRow, int[] moveCol) {
Queue<Combination> q = new LinkedList<Combination>();
int[][] distance = new int[maze.length][maze[0].length()]; //初期位置からの距離を格納しておくメモリ
Combination first = new Combination(startRow, startCol);
q.add(first); //初期状態
for(int r = 0; r < distance.length; r++) { //全データを-1で初期化
for(int c = 0; c < distance[r].length; c++) {
distance[r][c] = -1;
}
}
int count = 0; //移動回数
//幅優先探索
while(!q.isEmpty()) {
Combination now = q.poll();
for(int r = 0; r < moveRow.length; r++) {
Combination next = new Combination(now.getX() + moveRow[r], now.getY() + moveCol[r]);
if(next.getX() < 0 || next.getY() < 0) continue;
if(next.getX() > maze[0].length() || next.getY() > maze.length) continue;
if(distance[next.getX()][next.getY()] == -1 || (maze[next.getX()].charAt(next.getY())) == 'X') continue;
q.add(next);
distance[next.getX()][next.getY()] = count;
count++;
}
}
int max = Integer.MIN_VALUE;
for(int r = 0; r < distance.length; r++) { //最長距離を探査
for(int c = 0; c < distance[r].length; c++) {
if(distance[r][c] > max) max = distance[r][c];
}
}
return(max);
}
void doIt() {
String[] maze = {
"...",
"...",
"...",
};
int startRow = 0;
int startCol = 1;
int[] moveRow = {1, 0, -1, 0};
int[] moveCol = {0, 1, 0, -1};
System.out.println(longestPath(maze, startRow, startCol, moveRow, moveCol));
}
public static void main(String[] args) {
new Mazemaker().doIt();
}
class Combination {
private int x;
private int y;
Combination(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return(this.x);
}
public int getY() {
return(this.y);
}
}
}
答え:
int longestPath(String[] maze, int startRow, int startCol, int[] moveRow, int[] moveCol) {
int max = 0;
int width = maze[0].length(),
height = maze.length;
int[][] board = new int[height][width];
for(int r = 0; r < height; r++) {
for(int c = 0; c < width; c++) {
board[r][c] = -1;
}
}
board[startRow][startCol] = 0;
Queue<Integer> queueX = new LinkedList<Integer>();
Queue<Integer> queueY = new LinkedList<Integer>();
queueX.add(startCol);
queueY.add(startRow);
while(!queueX.isEmpty()) {
int x = queueX.poll();
int y = queueY.poll();
for(int r = 0; r < moveRow.length; r++) {
int nextX = x + moveCol[r],
nextY = y + moveRow[r];
if(0 <= nextX && nextX < width && 0 <= nextY && nextY < height && maze[nextY].charAt(nextX) == '.') {
board[nextY][nextX] = board[y][x] + 1;
queueX.add(nextX);
queueY.add(nextY);
}
}
}
for(int r = 0; r < height; r++) {
for(int c = 0; c < width; c++) {
if(maze[r].charAt(c) == '.' && board[r][c] == -1)
return(-1);
max = Math.max(max, board[r][c]);
}
}
return(max);
}