connect two path

Problem:
Given an n x n grid and two pair points (A, B) and (P, Q). determine if it is possible to connect the A to B and P to Q without intersecting paths. Valid paths are those composed only with straight vertical and/or horizontal lines -- diagonal lines are not permitted.

Definitions
each point (A, B) will have an x and y component.
the x axis is horizontal.
the y axis is vertical.
the point(0,0) is located at the top-left corner of the grid.
the point(n,n) is located at the bottom-right corner of the grid.


import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class oneD implements Comparable<oneD>{
    String name;
    int num;
    oneD(String name, int num) {
        this.name = name;
        this.num = num;
    }
    @Override
    public int compareTo(oneD o) {
        return this.num - o.num;
    }
    @Override
    public String toString() {
        return name + " " + num;
    }
}

public class ConnectTwoPaths {
    // return true if possible to connect A to B and P to A without intersecting paths.
    public static boolean find(int n, Cordinate A, Cordinate B, Cordinate P, Cordinate Q ) {
        print(n, A, B, P, Q);
        
        // if one of those point is not on boundary
        if (!onBounds(A, n) ||
            !onBounds(B, n) ||
            !onBounds(P, n) ||
            !onBounds(Q, n)) {
            return true;
        }
        
        oneD a = new oneD("A", convertToOneD(A, n));
        oneD b = new oneD("B",convertToOneD(B, n));
        oneD p = new oneD("P",convertToOneD(P, n));
        oneD q = new oneD("Q",convertToOneD(Q, n));
        
        oneD[] sorted = new oneD[] {a,b,p,q};
        Arrays.sort(sorted);
        
        Out.print(Arrays.toString(sorted));
        
        
        Set<oneD> set1 = new HashSet<>();
        set1.add(a);
        set1.add(b);
        Set<oneD> set2 = new HashSet<>();
        set2.add(p);
        set2.add(q);
        
        //points overlap
        if (set1.size() != 2 || set2.size() != 2) {
            return false;
        }
        
        if (set1.contains(sorted[0])) {
            if (set1.contains(sorted[1]) || set1.contains(sorted[3])) {
                return true;
            }
        }
        
        if (set2.contains(sorted[0])) {
            if (set2.contains(sorted[1]) || set2.contains(sorted[3])) {
                return true;
            }
        }
        
        return false;
    }
    
    private static int convertToOneD(Cordinate a, int n) {
        if (a.x == 0) {
            return a.y;
        }
        if (a.y == n) {
            return n + a.x;
        }
        if (a.x == n) {
            return 2*n + (n - a.y);
        }
        if (a.y == 0) {
            return 3 * n + (n - a.x);
        }
        return 0;
    }
    
    private static boolean onBounds(Cordinate a, int n) {
        if (a.x == 0 || a.x == n || a.y == 0 || a.y == n) {
            return true;
        }
        return false;
    }
    
    private static void print(int n, Cordinate A, Cordinate B, Cordinate P, Cordinate Q) {
        String[][] strs = new String[n+1][n+1];
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs.length; j++) {
                strs[i][j] = "#";
            }
        }
        strs[A.x][A.y] = "A";
        strs[B.x][B.y] = "B";
        strs[P.x][P.y] = "P";
        strs[Q.x][Q.y] = "Q";
        
        for (int i = 0; i < strs.length; i++) {
            for (int j = 0; j < strs.length; j++) {
                System.out.print(strs[i][j]);
            }
            Out.print("");
        } 
    }
    
    public static void main(String[] args) {
        Out.print(find(5,
                new Cordinate(0, 3), 
                new Cordinate(3, 5), 
                new Cordinate(2, 5), 
                new Cordinate(5, 3))); // false
        Out.print("");
        
        Out.print(find(5,
                new Cordinate(3, 5), 
                new Cordinate(5, 3), 
                new Cordinate(1, 5), 
                new Cordinate(3, 0))); // true
        Out.print("");
        
        Out.print(find(5,
                new Cordinate(3, 5), 
                new Cordinate(5, 3), 
                new Cordinate(1, 5), 
                new Cordinate(4, 5))); // false
        Out.print("");
        
        Out.print(find(5,
                new Cordinate(3, 5), 
                new Cordinate(5, 0), 
                new Cordinate(1, 5), 
                new Cordinate(4, 0))); // true
        Out.print(true);
        
        Out.print(find(5,
                new Cordinate(3, 3), 
                new Cordinate(5, 0), 
                new Cordinate(1, 5), 
                new Cordinate(4, 0))); // true
        
        Out.print(find(3,
                new Cordinate(3, 3), 
                new Cordinate(3, 0), 
                new Cordinate(3, 3), 
                new Cordinate(2, 0))); // false
        
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容