MazeSolver.java

/**
 * MazeSolve - Package: net.syamn.mazesolve
 * Created: 2013/02/07 6:29:35
 */
package net.syamn.mazesolve;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

/**
 * MazeSolver (MazeSolver.java)
 * @author syam(syamn)
 */
public class MazeSolver {
    public static void main(String[] args) {
        new MazeSolver().start();
    }
    
    List<String> data = new ArrayList<String>();
    private Block[][] map;
    private Block goal, start;
    private int xlen, ylen;
    
    private void start(){
        //readTest();
        read("C:\\maze.txt");
        mapping();
        
        search(goal.x, goal.y, 0);
        mark(start);
        
        print();
    }
    
    @SuppressWarnings("serial")
    private void readTest(){
        data = new ArrayList<String>(13) {{
            add("**************************");
            add("*S* *                    *");
            add("* * *  *  *************  *");
            add("* *   *    ************  *");
            add("*    *                   *");
            add("************** ***********");
            add("*                        *");
            add("** ***********************");
            add("*      *              G  *");
            add("*  *      *********** *  *");
            add("*    *        ******* *  *");
            add("*       *                *");
            add("**************************");
        }};
    }
    private void read(final String fileName){
        FileReader in = null;
        BufferedReader br = null;
        try{
            in = new FileReader(fileName);
            br = new BufferedReader(in);
            String line;
            while ((line = br.readLine()) != null) {
                data.add(line);
            }
        }catch (IOException ex){
            System.out.println("迷路ファイルの読み込みに失敗しました: " + ex.getMessage());
        }finally{
            if (br != null){
                try{ br.close(); }catch(Exception ignore){}
            }
            if (in != null){
                try{ in.close(); }catch(Exception ignore){}
            }
        }
    }
    private void mapping(){
        map = new Block[data.get(0).length()][data.size()];
        for (int y = 0; y < data.size(); y++){
            String line = data.get(y);
            for (int x = 0; x < line.length(); x++){
                Block block = new Block(x, y);
                switch (line.charAt(x)){
                    case '*': block.wall = true; break;
                    case 'S': block.start = true; start = block; break;
                    case 'G': block.goal = true; goal = block; break;
                }
                map[x][y] = block;
            }
        }
        xlen = map.length;
        ylen = map[0].length;
    }
    private void print(){
        for (int y = 0; y < map[0].length; y++){
            for (int x = 0; x < map.length; x++){
                System.out.print(map[x][y].getChar());
            }
            System.out.print("\n");
        }
    }
    
    private void search(int x, int y, int i){
        if (!isIn(x, y)) return;
        Block block = map[x][y];
        if (block.wall || (block.checked && block.i <= i)){
            return;
        }
        block.checked = true;
        block.i = i;
        
        i++;
        search(x + 1, y, i);
        search(x - 1, y, i);
        search(x, y + 1, i);
        search(x, y - 1, i);
    }
    private void mark(Block block){
        if (block.wall || block.goal){
            return;
        }
        block.correct = true;
        
        Block next = null;
        int min = Integer.MAX_VALUE;
        if (isIn(block.x + 1, block.y) && map[block.x + 1][block.y].i < min){
            next = map[block.x + 1][block.y];
            min = next.i;
        }
        if (isIn(block.x - 1, block.y) && map[block.x - 1][block.y].i < min){
            next = map[block.x - 1][block.y];
            min = next.i;
        }
        if (isIn(block.x, block.y + 1) && map[block.x][block.y + 1].i < min){
            next = map[block.x][block.y + 1];
            min = next.i;
        }
        if (isIn(block.x, block.y - 1) && map[block.x][block.y - 1].i < min){
            next = map[block.x][block.y - 1];
            min = next.i;
        }
        if (next == null){
            throw new IllegalStateException("この迷路はゴールに到達できません");
        }
        mark(next);
    }
    
    private boolean isIn(int x, int y){
        if (x < 0 || y < 0 || x >= xlen || y >= ylen){
            return false;
        }
        return true;
    }
    
    public class Block {
        public int x, y;
        public int i = Integer.MAX_VALUE;
        
        public boolean wall = false;
        public boolean start = false;
        public boolean goal = false;
        public boolean checked = false;
        public boolean correct = false;
        
        public Block(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        public char getChar(){
            if (wall) return '*';
            if (start) return 'S';
            if (goal) return 'G';
            if (correct) return '$';
            return ' ';
        }
        
        @Override
        public String toString(){
            return String.valueOf(getChar());
        }
    }
}