通过深度优先搜索产生的迷宫，深度优先搜索迷宫,[Java]代码pack

通过深度优先搜索产生的迷宫，深度优先搜索迷宫,[Java]代码pack

[Java]代码

package cn.outofmemory;import java.io.FileOutputStream;import java.io.IOException;import java.util.ArrayList;import java.util.Random;public class maziness {    private int M;//行数    private int N;//列数    private int[] visitMatrix;//搜索是判断是否曾被访问过    private int[][] colMatrix;//保存要输出的的'|'矩阵    private int[][] rowMatrix;//保存要输出的的'_'矩阵    private Random random;//用来生成随机数，保证迷宫的复杂程度    public maziness(int M ,int N){        this.M=M;        this.N=N;        visitMatrix=new int[M*N];        colMatrix = new int[M][N+1];        rowMatrix = new int[M+1][N];        init(colMatrix,M,N+1);        init(rowMatrix,M+1,N);        for (int i=0;i<M*N;i++)            visitMatrix[i]=0;        random = new Random();    }    private void init(int matrix[][],int M ,int N){        for (int i=0;i<M;i++)            for (int j=0;j<N;j++)                matrix[i][j]=1;    }    //返回num周围可用的邻居，即没被访问过，也没到达边缘    private void availableNeigbers(ArrayList<Integer> list,int num){        int allNeigber[]=new int[4];        if (num%N==1){            allNeigber[0]=num-N;            allNeigber[1]=num+N;            allNeigber[2]=num+1;            allNeigber[3]=-1;        }        else if (num%N==0){            allNeigber[0]=num-N;            allNeigber[1]=num+N;            allNeigber[2]=num-1;            allNeigber[3]=-1;        }        else{            allNeigber[0]=num-N;            allNeigber[1]=num+N;            allNeigber[2]=num-1;            allNeigber[3]=num+1;        }        for (int i=0;i<4;i++){            if (allNeigber[i]>0 & allNeigber[i]<=M*N)                if (visitMatrix[allNeigber[i]-1]==0 )                    list.add(allNeigber[i]);        }           }    //返回随机选出的可用邻居    private int neigber(int num){        ArrayList<Integer> list=new ArrayList<Integer>();        availableNeigbers(list,num);        if (list.isEmpty())            return -1;        else{            return (Integer) list.get(random.nextInt(list.size()));        }    }    //移除num1和num2之间的墙    private void removeWall(int num1,int num2){        int x1=(num1+N-1)/N-1;        int y1=(num1-1)%N;        if (Math.abs(num1-num2)==1){            if (num1>num2)                colMatrix[x1][y1]=0;            else                colMatrix[x1][y1+1]=0;        }        else {            if (num1>num2)                rowMatrix[x1-1][y1]=0;            else                rowMatrix[x1][y1]=0;        }    }    //生成迷宫    public void process(){          ArrayList<Integer> list=new ArrayList<Integer>();        int curr=(M*N)/2;        visitMatrix[curr-1]=1;        list.add(curr);        int tmp;        while (!list.isEmpty()){            tmp=neigber(curr);            if (tmp>0){                visitMatrix[tmp-1]=1;                removeWall(curr,tmp);                curr=tmp;                list.add(curr);            }            else                curr=(Integer) list.remove(list.size()-1);        }    }    //绘制迷宫，并输出到txt文件中    public void draw(FileOutputStream fos){        try {            fos.write(' ');            fos.write(' ');            for (int i=0;i<N-1;i++){                fos.write(' ');                fos.write('_');            }            fos.write('\r');            for (int i=0;i<M;i++){                int j;                for (j=0;j<N;j++){                    if (colMatrix[i][j]==1)                        fos.write('|');                    else                        fos.write(' ');                    if (rowMatrix[i][j]==1)                        fos.write('_');                    else                        fos.write(' ');                }                if (i!=M-1 || j!=N){                    fos.write('|');                    fos.write('\r');                }            }            fos.close();            } catch (IOException e) {            // TODO Auto-generated catch block            e.printStackTrace();        }    }    /**     * @param args     */    public static void main(String[] args) {        // TODO Auto-generated method stub        try {            FileOutputStream fos=new FileOutputStream("F://maze.txt");            maziness m=new maziness(30,60);            m.process();            m.draw(fos);        } catch (IOException e) {            // TODO Auto-generated catch block            e.printStackTrace();            System.out.println(e);        }    }}