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