ikemonn's blog

技術ネタをちょこちょこと

【TopCoder】SRM453.5 DIV2 Lv.1

問題文概略

迷路を脱出させるのにできるだけ長い距離を移動させたい時の、脱出までにかかる移動距離を求める。

書いたコード

import java.util.LinkedList;
import java.util.Queue;

public class MazeMaker {

    public 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];
        //すべての座標の値を-1にする(訪問したかどうかを判断するため)
        for (int i = 0; i < height; i++)
            for (int j = 0; j < width; j++)
                    board[i][j] = -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 i = 0; i < moveRow.length; i++) {
                //次の状態
                int nextX = x + moveCol[i],
                    nextY = y + moveRow[i];
                //次に移動するマスに移動できて、訪問済みかどうか判断
                if (   0 <= nextX && nextX < width
                    && 0 <= nextY && nextY < height
                    && board[nextY][nextX] == -1
                    && maze[nextY].charAt(nextX)  == '.' ) {
                        board[nextY][nextX] = board[y][x] + 1;
                        queueX.add(nextX);
                        queueY.add(nextY);
                }

            }

        }
        //各マスの値をチェックして出られる場合の最大の値を求める
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                //迷路から出られない時
                if(maze[i].charAt(j) == '.' && board[i][j] == -1)
                    return -1;
                //迷路から出られる場合の最大値
                max = Math.max(max, board[i][j]);
            }
        }
        return max;
    }

}

雑感

【TopCoder】SRM453.5 DIV2 Lv.2と同じく上記の本に載っていた問題。 探索に慣れよう。