PercolationDirectedNonrecursive.java
public class PercolationDirectedNonrecursive
{
public
static boolean[][] flow(boolean[][] open)
{
int N = open.length;
boolean[][] full = new boolean[N][N];
for (int j = 0; j < N; j++)
full[0][j] = open[0][j];
for (int i = 1; i < N; i++)
{
for (int j = 0; j < N; j++) {
boolean fill = false;
for (int k = j; (k < N) && open[i][k]; k++)
fill = fill ||
full[i-1][k];
for ( ; (j < N)
&& open[i][j]; j++)
if (fill) full[i][j] =
true;
}
}
return full;
}
public static boolean percolates(boolean[][] open)
{
boolean[][] full = flow(open);
int N = full.length;
for (int j = 0; j < N; j++)
if (full[N-1][j]) return true;
return false;
}
public static void show(boolean[][] a, boolean which)
{
int N = a.length;
StdDraw.setXscale(-1, N);
StdDraw.setYscale(-1, N);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (a[i][j] == which)
StdDraw.filledSquare(j, N-i-1,
.5);
}
public static boolean[][] random(int N, double p)
{
boolean[][] a = new boolean[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a[i][j] = StdRandom.bernoulli(p);
return
a;
}
public static void
main(String[] args)
{
boolean[][] open = StdArrayIO.readBoolean2D();
StdArrayIO.println(flow(open));
StdOut.println(percolates(open));
}
}
No comments:
Post a Comment