首页 > 其他 > 详细

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

时间:2014-12-21 09:12:30      阅读:306      评论:0      收藏:0      [点我收藏+]
在矩形网格中寻找最长的递增序列

比如如下网格

97,47,56,36
35,57,41,13
89,36,98,75
25,45,26,17

结果要求输出
17, 26, 36, 41, 47, 56, 57, 97

基本想法就是对图中的每一个点都当作起始点试一编
将序列最长的保存起来
最后输出

代码如下
使用java编写

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]){
					seek(bx+x,by+y);
					al.remove(al.size()-1);
				}	
	}
}



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

原文:http://blog.csdn.net/ylqhust/article/details/42054157

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!