Problem statement: Given a wire grid of size N * N with N-1 horizontal edges and N-1 vertical edges along the X and Y axis respectively, and a wire burning out every instant as per the given order using three matrices A, B, C such that the wire that burns is
(A[T], B[T] + 1), if C[T] = 0 or
(A[T] + 1, B[T]), if C[T] = 1
Determine the instant after which the circuit is broken
public static boolean checkConnections(int[] h, int[] v, int N) {
boolean[][] visited = new boolean[N][N];
dfs(h, v, visited,0,0);
return visited[N-1][N-1];
}
public static void dfs(int[]h, int[]v, boolean[][] visited, int i, int j) {
int N = visited.length;
if (i < N && j < N && i>= 0 && j >= 0 && !visited[i][j]) {
visited[i][j] = true;
if (v[i * (N-1) + j] == 1) {
dfs(h, v, visited, i, j+1);
}
if (h[i * (N-1) + j] == 1) {
dfs(h, v, visited, i+1, j);
}
if (i > 0 && h[(i-1)*(N-1) + j] == 1) {
dfs(h,v, visited, i-1, j);
}
if (j > 0 && h[(i * (N-1) + (j-1))] == 1) {
dfs(h,v, visited, i, j-1);
}
}
}
public static int burnout(int N, int[] A, int[] B, int[] C) {
int[] h = new int[N*N];
int[] v = new int[N*N];
for (int i = 0; i < N*N; i++) { h[i] = 1; v[i] = 1; }
for (int i = 0; i < N; i++) {
h[(i * (N)) + N - 1] = 0;
v[(N-1) * (N) + i] = 0;
}
System.out.println(printArray(h));
System.out.println(printArray(v));
for (int i = 0; i < A.length; i++) {
if (C[i] == 0) {
v[A[i] * (N-1) + B[i]] = 0;
} else {
h[A[i] * (N-1) + B[i]] = 0;
}
if (!checkConnections(h,v, N)) {
return i+1;
}
}
return -1;
}
int[] A = new int[9];
int[] B = new int[9];
int[] C = new int[9];
A[0] = 0; B [0] = 0; C[0] = 0;
A[1] = 1; B [1] = 1; C[1] = 1;
A[2] = 1; B [2] = 1; C[2] = 0;
A[3] = 2; B [3] = 1; C[3] = 0;
A[4] = 3; B [4] = 2; C[4] = 0;
A[5] = 2; B [5] = 2; C[5] = 1;
A[6] = 1; B [6] = 3; C[6] = 1;
A[7] = 0; B [7] = 1; C[7] = 0;
A[8] = 0; B [8] = 0; C[8] = 1;
System.out.println(burnout(9, A, B, C));
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
8
Alternatively,
public static boolean burnWiresAtT(int N, int[] A, int[] B, int[] C, int t) {
int[] h = new int[N*N];
int[] v = new int[N*N];
for (int i = 0; i < N*N; i++) { h[i] = 1; v[i] = 1; }
for (int i = 0; i < N; i++) {
h[(i * (N)) + N - 1] = 0;
v[(N-1) * (N) + i] = 0;
}
System.out.println(printArray(h));
System.out.println(printArray(v));
for (int i = 0; i < t; i++) {
if (C[i] == 0) {
v[A[i] * (N-1) + B[i]] = 0;
} else {
h[A[i] * (N-1) + B[i]] = 0;
}
}
return checkConnections(h, v, N);
}
public static int binarySearch(int N, int[] A, int[] B, int[] C, int start, int end) {
if (start == end) {
if (!burnWiresAtT(N, A, B, C, end)){
return end;
}
return -1;
} else {
int mid = (start + end)/2;
if (burnWiresAtT(N, A, B, C, mid)) {
return binarySearch(N, A, B, C, mid + 1, end);
} else {
return binarySearch(N, A, B, C, start, mid);
}
}
}
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
8
No comments:
Post a Comment