import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;
public class Test6 {
//随意写个2维数组做练练看测试,0代表空
int[][] lianliankanTu() {
int[][] tu = new int[4][4];
tu[0] = new int[] { 0, 0, 0, 1 };
tu[1] = new int[] { 3, 1, 0, 3 };
tu[2] = new int[] { 4, 1, 0, 0 };
tu[3] = new int[] { 1, 4, 0, 1 };
return tu;
}
public static void main(String[] args) {
Test6 t = new Test6();
int[][] tu = t.lianliankanTu();
LinkPoint point1 = t.new LinkPoint(1, 1);
LinkPoint point2 = t.new LinkPoint(3, 3);
boolean result = t.isLinked(tu, point1, point2);
System.out.println("result is " + result);
}
//存放与测试点可连的所有空值,用于判断是否有折线可连另一测试点
HashSet<LinkPoint> connected = new HashSet<LinkPoint>();
/**
* @param tu 图
* @param point1 测试点1
* @param point2 测试点2
* @return 是否可连
*/
boolean isLinked(int[][] tu, LinkPoint point1, LinkPoint point2) {
if (point1.obtainValue(tu) == point2.obtainValue(tu)) {
//判断是否有直线可连
if (obtainLinkedPoint(tu, point1, point2))
return true;
//判断是否有一折线可连
if (getCrossLinked(tu, point2))
return true;
//判断是否有二折线可连
if (getCrossLinked(tu, point2))
return true;
}
return false;
}
boolean obtainLinkedPoint(int[][] tu, LinkPoint point1, LinkPoint point2) {
//向下探索所有空值,直到碰到点
for (int row = point1.x + 1; row < tu.length; row++) {
LinkPoint lp = new LinkPoint(row, point1.y);
//如果该点就是测试点
if (lp.equals(point2))
return true;
//如果该点非空值,停止探索
if (!lp.isNull(tu))
break;
//set集合添加空点
connected.add(lp);
}
//向上探索
for (int row = point1.x - 1; row >= 0; row--) {
LinkPoint lp = new LinkPoint(row, point1.y);
if (lp.equals(point2))
return true;
if (!lp.isNull(tu))
break;
connected.add(lp);
}
//向右探索
for (int line = point1.y + 1; line < tu[0].length; line++) {
LinkPoint lp = new LinkPoint(point1.x, line);
if (lp.equals(point2))
return true;
if (!lp.isNull(tu))
break;
connected.add(lp);
}
//向左探索
for (int line = point1.y - 1; line >= 0; line--) {
LinkPoint lp = new LinkPoint(point1.x, line);
if (lp.equals(point2))
return true;
if (!lp.isNull(tu))
break;
connected.add(lp);
}
return false;
}
//获取转折点,通过将set集合的空点寻找垂直方向以及水平方向
//需要一份拷贝,否则报ConcurrentModifyException错误
boolean getCrossLinked(int[][] tu, LinkPoint point2) {
HashSet<LinkPoint> connectedClone = (HashSet<LinkPoint>) connected
.clone();
for (Iterator<LinkPoint> i = connectedClone.iterator(); i.hasNext();) {
LinkPoint point = i.next();
if (obtainLinkedPoint(tu, point, point2))
return true;
}
return false;
}
//一个结构类
class LinkPoint {
int x;
int y;
public LinkPoint(int x, int y) {
super();
this.x = x;
this.y = y;
}
int obtainValue(int[][] tu) {
return tu[x][y];
}
boolean isNull(int[][] tu) {
if (tu[x][y] == 0)
return true;
return false;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
LinkPoint other = (LinkPoint) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
@Override
public String toString() {
return "Point(" + x + "," + y + ")";
}
}
}