Check if There is a Valid Path in a GridLeetcode Problem 1391

原题

解决方案

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 
public class Solution {    public boolean hasValidPath(int[][] grid) {        City city = new City(grid);        Street street = city.get(city.entry());        return city.tryFromPortOfStartStreet(street.port1)            || city.tryFromPortOfStartStreet(street.port2);    }     public static void main(String[] args) {        Solution solution = new Solution();        int[][] grid = {            {4, 3, 1},            {6, 5, 1}        };        boolean result = solution.hasValidPath(grid);        System.out.println(result);    }} class City {    int[][] grid;    List<Street> streets = Street.streets();     City(int[][] grid) {        this.grid = grid;    }     boolean tryFromPortOfStartStreet(Point direction) {        Point location = entry();         while(true) {            //  1.  如果当前的位置就是出口            if (location.equals(exit())) {                return true;            }             //  2.  获得下一个位置            location = location.added(direction);             //  3.  获取下一个位置的 street            Street street = get(location);            //      空 代表 下一个位置超出边界            if (street == null) {                return false;            }             //  4.  尝试走进下一个位置的 street            //      获取出街的方向向量            direction = street.go(direction);            //      空 代表 下一个位置和当前位置没联通            if (direction == null) {                return false;            }        }    }      Point entry() {        return new Point(0, 0);    }     Point exit() {        int width = grid[0].length;        int height = grid.length;        return new Point(width - 1, height - 1);    }     Street get(Point location) {        int width = grid[0].length;        int height = grid.length;        if (   location.x < 0            || width <= location.x            || location.y < 0            || height <= location.y ) {            return null;        }        int streetNumber = grid[location.y][location.x];        return streets.get(streetNumber - 1);    }} class Street {    Point port1;    Point port2;     Street(Point port1, Point port2) {        this.port1 = port1;        this.port2 = port2;    }     static List<Street> streets() {        LinkedList<Street> streets = new LinkedList<>();        streets.add(new Street(Point.left, Point.right));        streets.add(new Street(Point.top, Point.bottom));        streets.add(new Street(Point.left, Point.bottom));        streets.add(new Street(Point.bottom, Point.right));        streets.add(new Street(Point.left, Point.top));        streets.add(new Street(Point.top, Point.right));        return streets;    }     boolean match(Point direction) {        Point expected = direction.flipped();        return port1.equals(expected) || port2.equals(expected);    }     Point go(Point direction) {        Point from = direction.flipped();        if (port1.equals(from)) {            return port2;         } else if (port2.equals(from)) {            return port1;         } else {            return null;        }    }     @Override    public String toString() {        return "Street " + port1 + " " + port2;    }} class Point {    public static Point left = new Point(-1, 0);    public static Point right = new Point(1, 0);    public static Point top = new Point(0, -1);    public static Point bottom = new Point(0, 1);     int x;    int y;     Point(int x, int y) {        this.x = x;        this.y = y;    }     Point added(Point delta) {        return new Point(x + delta.x, y + delta.y);    }     Point flipped() {        return new Point(-x, -y);    }     @Override    public boolean equals(Object o) {        if (this == o) return true;        if (o == null || getClass() != o.getClass()) return false;        Point point = (Point) o;        return x == point.x &&            y == point.y;    }     @Override    public int hashCode() {        return Objects.hash(x, y);    }     @Override    public String toString() {        return "(" + x + ", " + y + ")";    }}