连连看设计思路与java代码

时间:2022-03-14 16:07:40
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 + ")";
		}

	}

}