search.java

java实现的一个算法

package chess;

public class Search {
    int begin,count;
    int Pane[][];
    boolean visited[];
    int path[];
    int size;

    public Search(int size_,int begin_,int[][] pane_) {
        size=size_;count=0;
        Pane=pane_;
        begin=begin_;
        path=new int[size*size+1];
        visited=new boolean[size*size+1];
    //    System.out.print(path.length);
    }

    void Try(int begin_)
    {
        visited[begin_]=true;
        path[count++]=begin_;
        int i=1;
        while(i<visited.length )
        {
            if (visited[i] == true)
                i++;
            else break;
        }
        if(i==visited.length && canPass(begin_,begin))
        {
            path[path.length-1]=begin;
             for(int s=0;s<path.length;s++)
                 System.out.print(path[s]+",");
             System.out.println();
     //        count--;
             visited[begin_]=false;
        }

        else {
            int x=0,y=0;
            if(begin_%size==0)
            {
                y = size - 1;
                x=(begin_/size)-1;
            }
            else
                {
                    y = begin_ % size - 1;
                    x=begin_/size;
                }
            int lined[]=move(x,y);//
            for(int j=0;j<lined.length && lined[j]!=0;j++)
            {
                if(visited[lined[j]]==false)
                {
                    Try(lined[j]);
                    visited[lined[j]]=false;
                    count--;
                }

            }

        }
    }
    int[] move(int x,int y)
    {
        int[] lined=new int[8];
        int c=0;

        if(x+1<=size-1 && y-2>=0)
            lined[c++]=Pane[x+1][y-2];
        if(x+2<=size-1 && y-1>=0)
            lined[c++]=Pane[x+2][y-1];
        if(x+2<=size-1 && y+1<=size-1)
            lined[c++]=Pane[x+2][y+1];
        if(x+1<=size-1 && y+2<=size-1)
            lined[c++]=Pane[x+1][y+2];
        if(x-1>=0 && y+2<=size-1)
            lined[c++]=Pane[x-1][y+2];
        if(x-2>=0 && y+1<=size-1)
            lined[c++]=Pane[x-2][y+1];
        if(x-2>=0 && y-1>=0)
            lined[c++]=Pane[x-2][y-1];
        if(x-1>=0 && y-2>=0)
            lined[c++]=Pane[x-1][y-2];
        return lined;

    }

    boolean canPass(int node1,int node2)
    {
        int x1,y1,x2,y2;
        if(node1%size==0)
        {
            y1=size-1;
            x1=node1/size-1;
        }
        else
        {
            y1=node1%size-1;
            x1=node1/size;
        }

        if(node2%size==0)
        {
            y2=size-1;
            x2=node2/size-1;
        }
        else
        {
            y2=node2%size-1;
            x2=node2/size;
        }

        int[] lined=move(x1,y1);
        boolean flag=false;
        for(int i=0;i<lined.length && lined[i]!=0;i++)
            if(Pane[x2][y2]==lined[i])
            {
                flag = true;
                break;
            }
        return flag;
    }
}