public class SelfAvoidingWalk {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]); // lattice size
int T = Integer.parseInt(args[1]); // number of trials
int deadEnds = 0; // trials resulting in a dead end
// simulate T self-avoiding walks
for (int t = 0; t < T; t++) {
boolean[][] a = new boolean[N][N]; // intersections visited
int x = N/2, y = N/2; // current position
// repeatedly take a random step, unless you've already escaped
while (x > 0 && x < N-1 && y > 0 && y < N-1) {
// dead-end, so break out of loop
if (a[x-1][y] && a[x+1][y] && a[x][y-1] && a[x][y+1]) {
deadEnds++;
break;
}
// mark (x, y) as visited
a[x][y] = true;
// take a random step to unvisited neighbor
double r = Math.random();
if (r < 0.25) { if (!a[x+1][y]) x++; }
else if (r < 0.50) { if (!a[x-1][y]) x--; }
else if (r < 0.75) { if (!a[x][y+1]) y++; }
else if (r < 1.00) { if (!a[x][y-1]) y--; }
}
}
System.out.println(100*deadEnds/T + "% dead ends");
}
}
/*************************************************************************
* Generate T self-avoiding walks of length N.
* Report the fraction of time the random walk is non self-intersecting.
*
*************************************************************************/
Not Satisfied ? Just search & get the result
Related posts:
