読者です 読者をやめる 読者になる 読者になる

迷路の最短ルートを探索する

ネットでちょっと話題になっていたのでいまさらですがやってみた。
人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。

できるだけわかりやすく書こうとしたんだけど結局わかりずらくなってしまった。
移動できるポイントを配列に持ってループしながら上下左右を追うんじゃなくて
MazeDataクラスで管理したかったんだけど結局いけてない設計になってしまった。
Objectっぽくするとソースが複雑になるのはしょうがないのかなぁ

package jp.co.gara.maze;

import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Maze2 {

    public static void main(String[] args) throws Exception {
         new Maze2().solve();
    }

    private void solve() throws Exception {
         MazeData mazeData = new MazeData();
         mazeData.readFile();
         mazeData.execBfs();
         mazeData.print();
         System.out.println("end");
    }

    private class MazeData {
         private static final int width = 26;
         private static final int height = 13;
         Cell[][] map = new Cell[height][width];
         private Cell startCell;
         private Cell goalCell;

         public MazeData() {
              for (int i = 0; i < map.length; i++) {
                   for (int j = 0; j < map[0].length; j++) {
                        map[i][j] = new Cell(i, j);
                   }
              }
         }

         public Cell getUp(Cell nowCell) {
              return getCell(nowCell.x, nowCell.y + 1);
         }

         public Cell getDown(Cell nowCell) {
              return getCell(nowCell.x, nowCell.y - 1);
         }

         public Cell getRight(Cell nowCell) {
              return getCell(nowCell.x + 1, nowCell.y);
         }

         public Cell getLeft(Cell nowCell) {
              return getCell(nowCell.x - 1, nowCell.y);
         }

         private Cell getCell(int x, int y) {
              if (x < 0 || height <= x || y < 0 || width <= y) {
                   return null;
              }
              return map[x][y];
         }

         public void readFile() throws Exception {
              Scanner sc = new Scanner(
                        new FileInputStream(
                                  "C:/work/InputMaze.txt"));
              for (int i = 0; i < height; i++) {
                   String line = sc.nextLine();
                   char[] temp = line.toCharArray();
                   for (int j = 0; j < width; j++) {

                        Cell cell = getCell(i, j);
                        cell.setData(temp[j]);
                        if (temp[j] == 'S') {
                             startCell = cell;
                        } else if (temp[j] == 'G') {
                             goalCell = cell;
                        } else if (temp[j] == '*') {
                             cell.checked();
                        }
                   }
              }
         }

         public void execBfs() {
              Queue<Cell> queue = new LinkedList<Cell>();
              queue.add(startCell);
              int cost = 0;
              while (!queue.isEmpty()) {
                   cost++;
                   Cell cell = queue.poll();
                   Cell tmpCell = getDown(cell);
                   if (tmpCell != null && tmpCell.isNotCheck()) {
                        queue.add(tmpCell);
                        tmpCell.setCost(cost);
                        if (tmpCell == goalCell) {
                             break;
                        }
                   }
                   tmpCell = getUp(cell);
                   if (tmpCell != null && tmpCell.isNotCheck()) {
                        queue.add(tmpCell);
                        tmpCell.setCost(cost);
                        if (tmpCell == goalCell) {
                             break;
                        }
                   }
                   tmpCell = getLeft(cell);
                   if (tmpCell != null && tmpCell.isNotCheck()) {
                        queue.add(tmpCell);
                        tmpCell.setCost(cost);
                        if (tmpCell == goalCell) {
                             break;
                        }
                   }
                   tmpCell = getRight(cell);
                   if (tmpCell != null && tmpCell.isNotCheck()) {
                        queue.add(tmpCell);
                        tmpCell.setCost(cost);
                        if (tmpCell == goalCell) {
                             break;
                        }
                   }
              }
         }

         public void print() {
              Cell cell = goalCell;
              int cost = cell.getCost();
              while (cost > 1) {
                   cost--;
                   Cell tmpCell = getUp(cell);
                   if (tmpCell != null && tmpCell.getCost() == cost) {
                        tmpCell.setData('$');
                        cell = tmpCell;
                   }
                   tmpCell = getDown(cell);
                   if (tmpCell != null && tmpCell.getCost() == cost) {
                        tmpCell.setData('$');
                        cell = tmpCell;
                   }
                   tmpCell = getLeft(cell);
                   if (tmpCell != null && tmpCell.getCost() == cost) {
                        tmpCell.setData('$');
                        cell = tmpCell;
                   }
                   tmpCell = getRight(cell);
                   if (tmpCell != null && tmpCell.getCost() == cost) {
                        tmpCell.setData('$');
                        cell = tmpCell;
                   }
              }
              for (int i = 0; i < map.length; i++) {
                   for (int j = 0; j < map[0].length; j++) {
                        System.out.print(map[i][j]);
                   }
                   System.out.println("");
              }
         }

         private class Cell {("");][j]);ngth;
              int x = 0;
              int y = 0;
              private int cost = 0;
              private boolean isChecked = false;
              private char data = ' ';

              public Cell(int x, int y) {
                   this.x = x;
                   this.y = y;
              }

              public boolean isNotCheck() {
                   return !isChecked;
              }

              public void checked() {
                   isChecked = true;
              }

              public int getCost() {{ck()
                   return cost;
              }

              public void setCost(int cost) {
                   isChecked = true;
                   this.cost = cost;
              }

              public void setData(char c) {
                   data = c;
              }

              @Override
              public String toString() {
                   return String.valueOf(data);
              }
         }
    }

}
広告を非表示にする