我在做POJ 1054时,希望对自己定义的一个类Plant进行二分查找,但是查找的结果一直不成功(未找到)。我认为是没有实现判断类相等的接口中对应的方法,请问诸位该怎么实现,或者还是别的原因,烦请各位不吝赐教,谢谢!
以下是源代码,出问题的地方在searchPath方法中”当下一步在稻田内时,查找下一步的坐标是否在Plant[]中“,既:
if(Arrays.binarySearch(plants, tmp) != -1){
steps = 0;
break;
}
全部代码:
//POJ 1054
package week1;
import java.util.*;
public class The_Troublesome_frog {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int r = sc.nextInt();
int c = sc.nextInt();
int n = sc.nextInt();
Plant[] plants = new Plant[n];
//初始化
for(int i=0; i<n; i++){
plants[i] = new Plant();
plants[i].x = sc.nextInt();
plants[i].y = sc.nextInt();
}
Arrays.sort(plants);
int maxSteps = 2;
//选择plant[i]为第一个点,plants[j]为第二个点
for(int i=0; i<n-2;i++){
for(int j=i+1; j<n-1; j++){
int dx = plants[j].x - plants[i].x;
int dy = plants[j].y - plants[i].y;//在x和y方向上求得青蛙每一步的长度
int px = plants[i].x - dx;
int py = plants[i].y - dy;//求按照此步长,第一步之前的一步的位置
if(px > 1 && px < r && py > 1 && py < c)
continue;
//如果第一点的前一点在稻田内,说明第二点选的不合适,换一个点做第二点
int xMax = plants[i].x + (maxSteps - 1) * dx;
if(xMax > r)
break;
//未达到目前最长步数-1就出了稻田,说明这条路无法成为当前最长
//因为x是进过排序的,因此换第二个点只能使得出稻田更快,因此此时要换第一个点
int yMax = plants[i].y + (maxSteps - 1) * dy;
if(yMax > c || yMax < 1)
continue;
//Y方向过早越界,换第二个点
int steps = searchPath(plants[j], plants, dx, dy, r, c);
if (steps > maxSteps){
maxSteps = steps;
}
System.out.println("sec" + maxSteps);
}
System.out.println("fir" + maxSteps);
}
System.out.println("final" + maxSteps);
sc.close();
}
public static int searchPath(Plant secPlant, Plant[] plants, int dx, int dy, int r, int c){
Plant tmp = new Plant();//表示当前位置
tmp.x = secPlant.x + dx;
tmp.y = secPlant.y + dy;
int steps = 2;
while(tmp.x < r && tmp.x >1 && tmp.y < c && tmp.y > 1){
//当下一步在稻田内时,查找下一步的坐标是否在Plants[]中
if(Arrays.binarySearch(plants, tmp) != -1){
steps = 0;
break;
}
steps++;
tmp.x += dx;
tmp.y += dy;
}
return steps;
}
}
class Plant implements Comparable<Plant>{
int x;
int y;
public Plant(){
this.x = 0;
this.y = 0;
}
public int compareTo(Plant p) {
if(this.x > p.x){
return 1;
}
else{
if(this.x < p.x) return -1;
else{
if(this.y > p.y) return 1;
else return -1;
}
}
}
public boolean equals(Plant p){
if(this.x == p.x && this.y == p.y)
return true;
else return false;
}
}