【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攻略ガイド
- 作者: 高橋直大
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2012/09/29
- メディア: 大型本
- 購入: 9人 クリック: 319回
- この商品を含むブログ (7件) を見る
【TopCoder】SRM453.5 DIV2 Lv.2と同じく上記の本に載っていた問題。 探索に慣れよう。