求一道算法，奖励50块电话费

0 0

求一道算法，奖励50块电话费10

一组矩阵数据，位置大小都是随机分布的，假设每个矩阵数据都带有 canGet 的布尔属性。

规则是，假设一个矩阵的canGet被设为true，就会将所有与这个矩阵相交的矩阵的canGet也设为true。

设计一个算法，给出一些随机的矩阵并设置canGet为true，循环求出其中任何与之相交的矩阵也要设置canGet为true，假设当一个A矩阵canGet被设为true，它又会继续循环判断和A矩阵相交的矩阵，并设置canGet为true，重复下去，直到找到所有矩阵中canGet为true的矩阵数组。

最好性能上有优化。

谢谢啊，急求算法或者思路。或者提供哪些算法可以解决这类问题。

只要能帮助小弟解决目前难题，空中充值50块话费，50块不算什么的，一点心意回报，不坑人。

谢谢，问题不明白的再问问我，我表述能力有限，致歉。
或加我QQ544980720

问题补充：

chen_yongkai 写道

是正交矩阵吧

嗯，相交判断不用管，伪代码写如果相交就行了，谢谢。

问题补充：

kidding87 写道

矩阵相交的矩阵
怎么理解，或者怎么判断

矩阵相交不用关心，伪代码直接写如果相交就可以了，谢谢。

问题补充：

kidding87 写道

上面直接写的，我刚用ide写了个，调试了下，把注释也加上，你看是不是你需要的

public static void changeMatrix(List<Matrix> listStart ,List<Matrix> finds){
		  //判断时候初始的时候数据为空
		  if(finds==null||finds.size()==0||listStart.size()==0) return ;
		  //去掉查询过的数据，此处需要注意需重写Matrix的hashcode和equals方法
		  listStart.removeAll(finds); 
		  //零时变量
		  List temp =new ArrayList<Matrix>();
		  //遍历Matrix集合
	      for(int i=0;i<listStart.size();i++){
	    	  //遍历上次查询出来的结果
	        for(int j=0;j<finds.size();j++){
	        	//如果相交，则设置CanGet，并将结果放入temp中
	           if(isCross(listStart.get(i),finds.get(j))){
	             //setCanGet
	        	   temp.add(listStart.get(i));
	           }
	        }
	      }
	      //说明没有找到相交的结果集，退出递归
	      if(temp.size()==0) return ;
	      //向下一层继续查找
	      else  changeMatrix(listStart,temp);
	}

好的，我去尝试实现下，不懂的再问。

问题补充：

kidding87 写道

上面直接写的，我刚用ide写了个，调试了下，把注释也加上，你看是不是你需要的

public static void changeMatrix(List<Matrix> listStart ,List<Matrix> finds){
		  //判断时候初始的时候数据为空
		  if(finds==null||finds.size()==0||listStart.size()==0) return ;
		  //去掉查询过的数据，此处需要注意需重写Matrix的hashcode和equals方法
		  listStart.removeAll(finds); 
		  //零时变量
		  List temp =new ArrayList<Matrix>();
		  //遍历Matrix集合
	      for(int i=0;i<listStart.size();i++){
	    	  //遍历上次查询出来的结果
	        for(int j=0;j<finds.size();j++){
	        	//如果相交，则设置CanGet，并将结果放入temp中
	           if(isCross(listStart.get(i),finds.get(j))){
	             //setCanGet
	        	   temp.add(listStart.get(i));
	           }
	        }
	      }
	      //说明没有找到相交的结果集，退出递归
	      if(temp.size()==0) return ;
	      //向下一层继续查找
	      else  changeMatrix(listStart,temp);
	}

下班回家先，明天再去实现它，还有觉得这类算法计算量都好大？那个removeAll()算法也吃力

问题补充：

kidding87 写道

楼主说的有道理
广度优先好像也不是很好，这次用动态平衡实现

	public static void changeMatrix(List<Matrix> listStart ,List<Matrix> finds){
		  //判断时候初始的时候数据为空
		  if(finds==null||finds.size()==0||listStart.size()==0) return ;
              //List最好使用为LinkedList实现类
	     loop: for(Iterator<Matrix> i=listStart.iterator();i.hasNext();){
	    	 Matrix temp = i.next(); 
	        for(Iterator<Matrix> j=finds.iterator();j.hasNext();){
	           if(isCross(m,j.next())){
	             //setCanGet
	        	   finds.add(temp);
	        	   i.remove();
	        	   continue loop;
	           }
	        }
	      }
	}

大师，QQ什么时候在线呢，小弟请教。

算法

2012年4月17日 17:49

fenglijun
5
0 0 0

7个答案按时间排序按投票排序

0 0

采纳的答案

楼主说的有道理
广度优先好像也不是很好，这次用动态平衡实现

	public static void changeMatrix(List<Matrix> listStart ,List<Matrix> finds){
		  //判断时候初始的时候数据为空
		  if(finds==null||finds.size()==0||listStart.size()==0) return ;
              //List最好使用为LinkedList实现类
	     loop: for(Iterator<Matrix> i=listStart.iterator();i.hasNext();){
	    	 Matrix temp = i.next(); 
	        for(Iterator<Matrix> j=finds.iterator();j.hasNext();){
	           if(isCross(m,j.next())){
	             //setCanGet
	        	   finds.add(temp);
	        	   i.remove();
	        	   continue loop;
	           }
	        }
	      }
	}

2012年4月18日 21:22

kidding87
1566
1 1 19

添加评论

0 0

上面直接写的，我刚用ide写了个，调试了下，把注释也加上，你看是不是你需要的

public static void changeMatrix(List<Matrix> listStart ,List<Matrix> finds){
		  //判断时候初始的时候数据为空
		  if(finds==null||finds.size()==0||listStart.size()==0) return ;
		  //去掉查询过的数据，此处需要注意需重写Matrix的hashcode和equals方法
		  listStart.removeAll(finds); 
		  //零时变量
		  List temp =new ArrayList<Matrix>();
		  //遍历Matrix集合
	      for(int i=0;i<listStart.size();i++){
	    	  //遍历上次查询出来的结果
	        for(int j=0;j<finds.size();j++){
	        	//如果相交，则设置CanGet，并将结果放入temp中
	           if(isCross(listStart.get(i),finds.get(j))){
	             //setCanGet
	        	   temp.add(listStart.get(i));
	           }
	        }
	      }
	      //说明没有找到相交的结果集，退出递归
	      if(temp.size()==0) return ;
	      //向下一层继续查找
	      else  changeMatrix(listStart,temp);
	}

2012年4月18日 16:40

kidding87
1566
1 1 19

添加评论

0 0

广度优先算法
楼主还有什么不清楚的么？

2012年4月18日 15:40

kidding87
1566
1 1 19

添加评论

0 0

	public void changeMatrix(List<Matrix> listStart ,List<Matrix> finds){
		  listStart.removeAll(finds);
		  List temp =new ArrayList<Matrix>();
	      for(int i=0;i<listStart.size();i++){
	        for(int j=0;j<finds.size();j++){
	           if(isCross(listStart.get(i),finds.get(j))){
	             //setCanGet
	        	   temp.add(i);
	           }
	        }
	      }
	      changeMatrix(listStart,temp);
	}

2012年4月18日 15:23

kidding87
1566
1 1 19