数据结构-迷宫算法-java实现

package com.citi.ww03140.ds.maze;

public class Cell {

    private int i;

    private int j;

    public int getI() {
        return i;
    }

    public void setI(int i) {
        this.i = i;
    }

    public int getJ() {
        return j;
    }

    public void setJ(int j) {
        this.j = j;
    }

    public Cell(int i, int j) {
        this.i = i;
        this.j = j;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + i;
        result = prime * result + j;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Cell other = (Cell) obj;
        if (i != other.i)
            return false;
        if (j != other.j)
            return false;
        return true;
    }

}

package com.citi.ww03140.ds.maze;

import java.util.Stack;

public class Maze {

    private final int BLIND_SIZE=3;

    public final static int WALL=-1;

    public final static int PASSAGE_WAY=0;

    private final Stack<Cell> path=new Stack<Cell>();

    private int[][] grids=new int[0][0];

    private Cell exitCell;

    private Cell curCell=new Cell(0,0);

    public Cell getExitCell() {
        return exitCell;
    }

    public void setExitCell(Cell exitCell) {
        this.exitCell = exitCell;
    }

    public Cell getCurCell() {
        return curCell;
    }

    public void setCurCell(Cell curCell) {
        this.curCell = curCell;
    }

    public Maze(int[][] grids, int ei,int ej){
        this.grids=grids;
        exitCell=new Cell(ei,ej);
    }

    public int[][] getGrids() {
        return grids;
    }

    public void seekPath(){

        //while(!curCell.equals(exitCell)){
        //    System.out.println(curCell.getI()+","+curCell.getJ());
            grids[curCell.getI()][curCell.getJ()]=(grids[curCell.getI()][curCell.getJ()]+2);
            Cell ncell=nextCell(curCell.getI(),curCell.getJ());
            if(ncell==null){
                grids[curCell.getI()][curCell.getJ()]=BLIND_SIZE;
                path.pop();
                ncell=path.peek();
            }
            curCell=ncell;
            if(!path.contains(curCell)){
                path.push(curCell);
            }
        //}
        printResult();
    }

    private void printResult(){
        for(int i=0;i<grids.length;i++){
            for(int j=0;j<grids[i].length;j++){
                System.out.print(grids[i][j]+",  ");
            }
            System.out.println();
        }
    }
    /**
     * 四个方向寻找出路
     * @param i
     * @param j
     * @return
     */
    private Cell nextCell(int i,int j){
        Cell ncell=detectNorthGrid(i,j);
        if(ncell!=null){
            return ncell;
        }
        Cell wcell=detectWestGrid(i,j);
        if(wcell!=null){
            return wcell;
        }
        Cell ecell=detectEastGrid(i,j);
        if(ecell!=null){
            return ecell;
        }
        Cell scell=detectSouthGrid(i,j);
        if(scell!=null){
            return scell;
        }
        return null;
    }


    protected void setBlindSide(int i, int j){
        grids[i][j]=BLIND_SIZE;
    }

    private Cell detectEastGrid(int i, int j){
        if(j+1>=grids[i].length){
            return null;
        }
        int eastGrid=grids[i][j+1];
        return getCell(i, j+1, eastGrid);
    }

    private Cell detectWestGrid(int i, int j){
        if(j-1<0){
            return null;
        }
        int eastGrid=grids[i][j-1];
        return getCell(i, j-1, eastGrid);
    }

    private Cell getCell(int i, int j, int eastGrid) {
        if(eastGrid==0){
            return new Cell(i,j);
        }
        return null;
    }

    private Cell detectNorthGrid(int i, int j){
        if(i-1<0){
            return null;
        }
        int eastGrid=grids[i-1][j];
        return getCell(i-1, j, eastGrid);
    }

    private Cell detectSouthGrid(int i, int j){
        if(i+1>=grids.length){
            return null;
        }
        int eastGrid=grids[i+1][j];
        return getCell(i+1, j, eastGrid);
    }

    public static void main(String[] args){

        //maze.seekPath(0, 0);
    }
}

package com.citi.ww03140.ds.maze;

import java.awt.Color;
import java.awt.Graphics;
import java.util.TimerTask;

import javax.swing.JFrame;
import javax.swing.JPanel;

@SuppressWarnings("serial")
public class MazeFrame extends JFrame {

    private final Maze maze;

    private final int LEN=50;

    private final int[][] grids = {
            {0,0,1,0,0,0,1,1},
            {1,0,0,0,1,0,0,0},
            {0,1,1,0,0,0,1,0},
            {0,1,0,0,1,0,0,0},
            {1,0,0,1,0,0,0,1},
            {0,0,0,0,0,1,0,0}
            };

    private final java.util.Timer timer = new java.util.Timer();

    public MazeFrame() {
        setTitle("Maze");
        getContentPane().add(new ArcsPanel());

        maze=new Maze(grids,5,7);
        //timer
        timer.schedule(new TimerTask() {
            @Override
            public void run() {
                if(!maze.getCurCell().equals(maze.getExitCell())){
                    repaint();
                }
            }
        }, 0, 1000);
    }

    public static void main(String[] args) {
        MazeFrame frame = new MazeFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(500, 500);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }

    class ArcsPanel extends JPanel {
        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);
            maze.seekPath();
            draw(g);
        }

        private void draw(Graphics g){
           int[][] grids= maze.getGrids();
           for(int i=0;i<grids.length;i++){
               for(int j=0;j<grids[i].length;j++){

                   if(grids[i][j]==0){
                       g.setColor(Color.BLUE);
                       g.drawRect(i*LEN, j*LEN, LEN, LEN);
                   }else if(grids[i][j]!=0){
                       g.setColor(Color.BLACK);
                       g.fillRect(i*LEN, j*LEN, LEN, LEN);
                   }
                   if(grids[i][j]%2==0){
                       g.setColor(Color.ORANGE);
                       g.drawRect(i*LEN, j*LEN, LEN, LEN);
                   }
                   if(i==maze.getCurCell().getI() && j==maze.getCurCell().getJ()){
                       g.setColor(Color.YELLOW);
                       g.fillRect(i*LEN, j*LEN, LEN, LEN);
                   }
               }
           }
        }

    }
}