首页 > 代码库 > 矩形网格中寻找最长递增序列

矩形网格中寻找最长递增序列

import java.util.ArrayList;

public class 最长递增序列 {
	static int[][] rect={
			{97,47,56,36},
			{35,57,41,13},
			{89,36,98,75},
			{25,45,26,17}
	};
	static ArrayList<String> al=new ArrayList<String>();
	static ArrayList<String> longMax=new ArrayList<String>();
	public static void main(String[] args){
		
		for(int i=0;i<rect.length;i++)
			for(int j=0;j<rect[0].length;j++){
				seek(i,j);
				al=new ArrayList<String>();
			}
		System.out.println(longMax);
	}
	public static void seek(int bx,int by){
		al.add(rect[bx][by]+"");
		if(al.size()>longMax.size())
			longMax=new ArrayList(al);
		for(int x=-1;x<=1;x++)
			for(int y=-1;y<=1;y++)
				if(0<=bx+x && 0<=by+y && bx+x<=3 && by+y<=3 && rect[bx][by]<rect[bx+x][by+y]){
					ArrayList<String> temp=new ArrayList<String>(al);
					seek(bx+x,by+y);
					al=temp;
				}	
	}

}<pre name="code" class="html"><pre name="code" class="html">下面的代码将已经试过某一个网格的最长路径保存了下来,这样再次调用时就可以直接使用

import java.util.ArrayList;

public class 最长递增序列 {

	static int[][] rect={
			{97,47,56,36},
			{35,57,41,13},
			{89,36,98,75},
			{25,45,26,17}
	};
	static ArrayList<Integer> al=new ArrayList<Integer>();
	static ArrayList<Integer> longMax=new ArrayList<Integer>();
	static ArrayList<Integer> partMax=new ArrayList<Integer>();
	static int[][][] stoal=new int[rect.length][rect[0].length][rect.length*rect[0].length];
	public static void main(String[] args){
		
		for(int i=0;i<rect.length;i++)
			for(int j=0;j<rect[0].length;j++){
				seek(i,j);
				memery(i,j);
				al=new ArrayList<Integer>();
			}
		System.out.println(longMax);
	}
	public static void seek(int bx,int by){
		if(stoal[bx][by][0]!=0){
			for(int l=0;l<stoal[bx][by].length && stoal[bx][by][l]!=0;l++)
			al.add(stoal[bx][by][l]);
			if(al.size()>longMax.size())
				longMax=new ArrayList(al);
			if(al.size()>partMax.size())
				partMax=new ArrayList(al);
			return;
			}
		al.add(rect[bx][by]);
		if(al.size()>longMax.size())
			longMax=new ArrayList(al);
		if(al.size()>partMax.size())
			partMax=new ArrayList(al);
		for(int x=-1;x<=1;x++)
			for(int y=-1;y<=1;y++)
				if(0<=bx+x && 0<=by+y && bx+x<=3 && by+y<=3 && rect[bx][by]<rect[bx+x][by+y]){
					ArrayList<Integer> temp=new ArrayList<Integer>(al);
					seek(bx+x,by+y);
					al=temp;
				}	
	}
	public static void memery(int i,int j){
		int len=partMax.size();
		for(int k=0;k<len;k++)
			stoal[i][j][k]=partMax.remove(0);
	}
}



矩形网格中寻找最长递增序列