java使用Union Find从topbtm查找路径
问题
- 有一条从田地顶部到底部的路径吗
- 如果添加了圆形传感器区域，是否仍有路径
- 在仍有路径的情况下，可以添加多少传感器
我试过的
- 创建了一个二维数组
- 使用UnionFind算法查找左上角是否可以到达左下角
- 使用三角学在二维数组中创建'-1'的圆形轮廓，以表示无法通过的区域
输入
- 雷达的数量
- X中心位置，Y中心位置，半径
预期产量
- 可以放置的雷达数量，同时仍有从顶部开始的路径-->；btm
代码及；示例
给定输入：
6 36 228 58 164 224 58 88 170 42 93 105 42 167 85 58 28 44 58
输出为5，但预期为2（第三台雷达将阻止顶部的路径-->；btm
我需要什么帮助
朝着我做错的方向前进，或者朝着我需要寻找的方向前进。 我认为UnionFind创建工会的方式有问题，和/或测试是否存在从顶部到底部的路径
代码
Uion查找代码
public static class UnionFind {
// The number of elements in this union find
private int size;
// Used to track the size of each of the component
private int[] sz;
// id[i] points to the parent of i, if id[i] = i then i is a root node
private int[] id;
// Tracks the number of components in the union find
private int numComponents;
public UnionFind(int size) {
if (size <= 0)
throw new IllegalArgumentException("Size <= 0 is not allowed");
this.size = numComponents = size;
sz = new int[size];
id = new int[size];
for(int i = 0; i < size; i++) {
id[i] = i; // Link to itself (self root)
sz[i] = 1; // Each component is originally of size one
}
}
// Find which component/set 'p' belongs to, takes amortized constant time.
public int find(int p) {
// Find the root of the component/set
int root = p;
while( root != id[root] )
root = id[root];
// Compress the path leading back to the root.
// Doing this operation is called "path compression"
// and is what gives us amortized time complexity.
while(p != root) {
int next = id[p];
id[p] = root;
p = next;
}
return root;
}
// This is an alternative recursive formulation for the find method
// public int find(int p) {
// if (p == id[p]) return p;
// return id[p] = find(id[p]);
// }
// Return whether or not the elements 'p' and
// 'q' are in the same components/set.
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// Return the size of the components/set 'p' belongs to
public int componentSize(int p) {
return sz[find(p)];
}
// Return the number of elements in this UnionFind/Disjoint set
public int size() {
return size;
}
// Returns the number of remaining components/sets
public int components() {
return numComponents;
}
// Unify the components/sets containing elements 'p' and 'q'
public void unify(int p, int q) {
int root1 = find(p);
int root2 = find(q);
// These elements are already in the same group!
if (root1 == root2) return;
// Merge smaller component/set into the larger one.
if (sz[root1] < sz[root2]) {
sz[root2] += sz[root1];
id[root1] = root2;
} else {
sz[root1] += sz[root2];
id[root2] = root1;
}
// Since the roots found are different we know that the
// number of components/sets has decreased by one
numComponents--;
}
}
主课
import static java.lang.Math.cos;
import static java.lang.Math.sin;
import java.util.Scanner;
public class Travel {
public static final int HEIGHT = 300;
public static final int WIDTH = 200;
private static int getID(int row, int col) {
return (row*WIDTH) + col;
}
private static void drawCircle(int x, int y, int r, int[][] field) {
double PI = 3.1415926535;
double i, angle, x1, y1;
for (i=0; i<360;i++) {
angle = i;
x1 = r * cos((angle * PI) / 180);
y1 = r * sin((angle * PI) / 180);
int ElX = (int) Math.round(x+x1);
int ElY = (int) Math.round(y+y1);
if ((ElX < 0) || (ElX > (WIDTH-1))) {
continue;
}
if ((ElY < 0) || (ElY > (HEIGHT-1))) {
continue;
}
// System.out.println("The current X:" + x);
// System.out.println("The current Y:" + y);
//
// System.out.println("The current ElX: " + ElX);
// System.out.println("The current ElY: " + ElY);
// System.out.println("");
field[ElY][ElX] = -1;
}
}
public static void main(String[] args) {
// setup initial field
int[][] field = new int[HEIGHT][WIDTH];
for (int row=0; row<HEIGHT; row++) {
for (int col=0; col<WIDTH; col++) {
field[row][col] = 0;
}
}
// for (int row=0; row < HEIGHT; row++) {
// for (int col=0; col < WIDTH; col++) {
// if (row==0) {
// field[row][col] = 1;
// } else if(row==HEIGHT-1) {
// field[row][col] = 0;
// } else {
// field[row][col] = WIDTH*row+col;
// }
// }
// }
Scanner in = new Scanner(System.in);
int numOfSensors = in.nextInt();
int numOfSensorsOnField = 0;
UnionFind uf = new UnionFind(HEIGHT*WIDTH);
for(int i=0; i<numOfSensors; i++) {
int x = in.nextInt();
int y = in.nextInt();
int r = in.nextInt();
//field[y][x] = -1;
drawCircle(x, y, r, field);
numOfSensorsOnField++;
for (int row=0; row < HEIGHT; row++) {
for (int col = 0 ; col < WIDTH; col++) {
if ((row < (HEIGHT-1)) && (field[row][col]==field[row+1][col])) {
uf.unify(getID(row,col), getID(row+1, col));
}
if ((col < (WIDTH -1)) && (field[row][col]==field[row][col+1])) {
uf.unify(getID(row,col), getID(row, col+1));
}
}
}
boolean bottom = false;
// for (int col=0; col<WIDTH; col++) {
// for (int colBtm=col; col<WIDTH; col++) {
// if(uf.find(getID(0,col)) == uf.find(getID(HEIGHT-1, colBtm))) {
// bottom = true;
// }
// }
// }
if(uf.find(getID(0,0)) == uf.find(getID(HEIGHT-1,WIDTH-1))){
System.out.println(uf.find(getID(0,0)));
bottom = true;
}
System.out.println("Boolean is: " + bottom);
if (!bottom) {
break;
}
}
//in.nextInt();
// for (int row=0; row < HEIGHT; row++) {
// for (int col=0; col < WIDTH; col++) {
// System.out.print(field[row][col]);
// System.out.print("\t");
// }
// System.out.println();
// }
System.out.println(numOfSensorsOnField-1);
}
}
共 (0) 个答案