高级农民
- 积分
- 2934
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2020-1-21
- 最后登录
- 1970-1-1
|
写起来还真的很长- public class UnboundMatrix {
- private Map<Integer, TreeSet<Integer>> xMap;
- private Map<Integer, TreeSet<Integer>> yMap;
- private Map<String, String> parent;
- public UnboundMatrix() {
- xMap = new HashMap<>();
- yMap = new HashMap<>();
- parent = new HashMap<>();
- }
- public void updatePosition(int x, int y) {
- int[] cur = {x, y};
- xMap.putIfAbsent(x, new TreeSet<>());
- yMap.putIfAbsent(y, new TreeSet<>());
- Set<Integer> x1 = xMap.get(x + 1);
- if (x1 != null && x1.contains(y)) {
- union(cur, new int[]{x + 1, y});
- }
- Set<Integer> x2 = xMap.get(x - 1);
- if (x2 != null && x2.contains(y)) {
- union(cur, new int[]{x - 1, y});
- }
- Set<Integer> y1 = yMap.get(y + 1);
- if (y1 != null && y1.contains(x)) {
- union(cur, new int[]{x, y + 1});
- }
- Set<Integer> y2 = yMap.get(y - 1);
- if (y2 != null && y2.contains(x)) {
- union(cur, new int[]{x, y - 1});
- }
- xMap.get(x).add(y);
- yMap.get(y).add(x);
- }
- public String find(int[] a) {
- StringBuilder sb = new StringBuilder();
- sb.append(a[0]).append(",").append(a[1]);
- return find(sb.toString());
- }
- private String find(String node) {
- if (!parent.containsKey(node)) parent.put(node, node);
- if (!parent.get(node).equals(node)) {
- parent.put(node, find(parent.get(node))); // Path compression
- }
- return parent.get(node);
- }
- public void union(int[] a, int[] b) {
- String root1 = find(a);
- String root2 = find(b);
- if (!root1.equals(root2)) {
- parent.put(root1, root2); // Union by rank can be added for optimization
- }
- }
- public boolean isConnected(int[] a, int[] b) {
- return find(a).equals(find(b));
- }
- public int minStep(int[] a, int[] b) {
- TreeSet<Integer> aySet = xMap.get(a[0]);
- TreeSet<Integer> axSet = yMap.get(a[1]);
- if (axSet == null || aySet == null) {
- return -1;
- }
- TreeSet<Integer> bySet = xMap.get(b[0]);
- TreeSet<Integer> bxSet = yMap.get(b[1]);
- if (bxSet == null || bySet == null) {
- return -1;
- }
- Queue<int[]> queue = new ArrayDeque<>();
- Set<int[]> visited = new HashSet<>();
- queue.offer(a);
- visited.add(a);
- int step = 0;
- while(!queue.isEmpty()) {
- for (int size = queue.size(); size > 0; size--) {
- int[] cur = queue.poll();
- if (cur[0] == b[0] && cur[1] == b[1]) {
- return step;
- }
- TreeSet<Integer> curySet = xMap.get(cur[0]);
- TreeSet<Integer> curxSet = yMap.get(cur[1]);
- for (int y: curySet) {
- int[] next = {cur[0], y};
- if(visited.add(next)) {
- queue.offer(next);
- }
- }
- for (int x: curxSet) {
- int[] next = {x, cur[1]};
- if(visited.add(next)) {
- queue.offer(next);
- }
- }
- }
- step++;
- }
- return step;
- }
- }
复制代码 |
|