import java.util.*;
import java.io.*;
import static java.
util.
Arrays.
*; import static java.
lang.
Math.
*;
public class RandomMaze {
int MAX = 30;
boolean[][][] map;
int[][] arrow;
LinkedList<int[]> route;
HashSet<P> used, route_h;
int sx = 1, sy = 1, ex = MAX, ey = MAX;
int LEN = MAX / 2;
MyDirect direct;
int[] dx = {-1,0,1,0};
int[] dy = {0,-1,0,1};
public RandomMaze() {
// TODO 自動生成されたコンストラクター・スタブ
map = new boolean[MAX+2][MAX+2][4];
arrow = new int[MAX+2][MAX+2];
for (int[] a : arrow) fill(a, -1);
for (int i=0;i<MAX+2;i++) {
map[i][1][0] = map[i][0][2] = map[1][i][1] = map[0][i][3] = true;
map[i][MAX][2] = map[i][MAX+1][0] = map[MAX][i][3] = map[MAX+1][i][1] = true;
arrow[i][0] = arrow[i][MAX+1] = 1; arrow[0][i] = arrow[MAX+1][i] = 0;
}
route = new LinkedList<int[]>();
route_h = new HashSet<P>();
used = new HashSet<P>();
direct = new MyDirect();
// print_board();
create_route();
// print_board();
while (! is_finish()) {
P[] puts = next_puts();
int r = rnd.nextInt(puts.length);
create_branch(puts[r].x, puts[r].y, puts[r].d);
}
print_board();
}
P[] next_puts() {
ArrayList<P> puts = new ArrayList<P>();
for (int y=1;y<=MAX;y++) for (int x=1;x<=MAX;x++) {
if (arrow[y][x] >= 0) continue;
for (int i=0;i<4;i++){
if (map[y][x][i]) continue;
if (arrow[y+dy[i]][x+dx[i]] < 0) continue;
puts.add(new P(x, y, (i+2)%4));
break;
}
}
return puts.toArray(new P[]{});
}
public void create_route() {
int x = sx, y = sy, d = -1;
while (x != ex || y != ey) {
int nd = next(x, y, d, direct);
// debug(x, y, d);
if (nd < 0) {
used.add(new P(x, y));
arrow[y][x] = 0;
int[] undo = route.removeLast();
int px = undo[0], py = undo[1], pd = undo[2];
x = px; y = py; d = pd;
if (route_h.remove(new P(x, y))) {
// debug("ok");
// new Scanner(System.in).next();
// print_board();
}
continue;
}
route.add(new int[]{x, y, d});
d = nd;
arrow[y][x] = d;
route_h.add(new P(x, y));
used.add(new P(x, y));
x += dx[d]; y += dy[d];
create_wall(x, y, d);
}
route.add(new int[]{ex, ey, 2});
route_h.add(new P(ex, ey));
used.add(new P(ex, ey));
}
private boolean on_route(int x, int y) {
return route_h.contains(new P(x, y));
}
private boolean used(int x, int y) {
return used.contains(new P(x, y));
}
public void create_branch(int cx, int cy, int cd) {
int x = cx, y = cy, d = cd;
Branch branch = new Branch();
for(int cnt = 0;cnt < LEN;cnt++) {
used.add(new P(x, y));
arrow[y][x] = d;
create_wall(x, y, d);
int nd = next(x, y, d, branch);
if (nd < 0) return;
int nx = x + dx[nd], ny = y + dy[nd];
x = nx; y = ny; d = nd;
}
}
private int next(int x, int y, int d, Direct direct) {
boolean[] f = new boolean[4];
for (int i=0;i<4;i++) {
if (i == (d+2)%4) {
f[i] = true;
continue;
}
if (arrow[y+dy[i]][x+dx[i]] >= 0) {
f[i] = true;
int arr = arrow[y+dy[i]][x+dx[i]];
f[arr] = true;
}
}
if (f[0] & f[1] & f[2] & f[3]) return -1;
int dir;
do {
dir = direct.direct(x, y);
} while(f[dir]);
// print_board();
return dir;
}
private void create_wall(int x, int y, int d) {
for (int i=0;i<4;i++) if(i != (d+2)%4) {
map[y][x][i] = map[y+dy[i]][x+dx[i]][(i+2)%4] |= used(x+dx[i], y+dy[i]);
}
}
private boolean is_finish() {
return used.size() == MAX * MAX;
}
public void print_board() {
for (int i=0;i<MAX*2+1;i++) {
int y = i / 2 + 1;
if (i % 2 == 0) {
for (int x=1;x<=MAX;x++) {
if (map
[y
][x
][1]) System.
out.
print("-"); }
} else {
for (int x=1;x<=MAX+1;x++) {
if (map
[y
][x
][0]) System.
out.
print("|"); if (x == MAX+1) break;
if (sx
== x
&& sy
== y
) System.
out.
print("#"); else if (ex
== x
&& ey
== y
) System.
out.
print("*"); else if (on_route
(x, y
)) System.
out.
print("o"); else if (used
(x, y
)) System.
out.
print(" "); }
}
}
}
class P {
int x, y, d;
P(int x, int y) {
this.x = x;
this.y = y;
d = 0;
}
P(int x, int y, int d) {
this.x = x;
this.y = y;
this.d = d;
}
public int hashCode() {
return x * MAX + y;
}
public boolean equals
(Object o
) { if (o instanceof P) {
P p = (P) o;
return x == p.x && y == p.y;
}
return false;
}
}
interface Direct {
int direct(int x, int y);
}
class MyDirect implements Direct{
double[][] waights = {
{0.40, 0.50, 0.90, 1.0},
{0.45, 0.50, 0.55, 1.0},
{0.05, 0.50, 0.95, 1.0},
{0.45, 0.50, 0.55, 1.0},
{0.15, 0.30, 0.65, 1.0}
};
int[] waight_d;
int div;
public MyDirect() {
waight_d = new int[waights.length + 1];
div = (2 * MAX / waights.length);
for (int i=1;i<=waights.length;i++) {
waight_d[i] = div * i;
}
}
public int direct(int x, int y) {
// TODO 自動生成されたメソッド・スタブ
double r = rnd.nextDouble();
int area = (x + y) / div;
for (int i=0;;i++) if (r < waights[area][i]){
return i;
}
}
}
class Branch implements Direct{
public Branch() {
// TODO 自動生成されたコンストラクター・スタブ
}
public int direct(int x, int y) {
// TODO 自動生成されたメソッド・スタブ
return rnd.nextInt(4);
}
}
}
public static void main
(String[] args
) { new RandomMaze();
}
}
CmltcG9ydCBqYXZhLnV0aWwuKjsKaW1wb3J0IGphdmEuaW8uKjsKCmltcG9ydCBzdGF0aWMgamF2YS51dGlsLkFycmF5cy4qOwppbXBvcnQgc3RhdGljIGphdmEudXRpbC5Db2xsZWN0aW9ucy4qOwppbXBvcnQgc3RhdGljIGphdmEubGFuZy5NYXRoLio7CgpwdWJsaWMgY2xhc3MgUmFuZG9tTWF6ZSB7CgoJaW50IE1BWCA9IDMwOwoJYm9vbGVhbltdW11bXSBtYXA7CglpbnRbXVtdIGFycm93OwoJTGlua2VkTGlzdDxpbnRbXT4gcm91dGU7CglIYXNoU2V0PFA+IHVzZWQsIHJvdXRlX2g7CglpbnQgc3ggPSAxLCBzeSA9IDEsIGV4ID0gTUFYLCBleSA9IE1BWDsKCWludCBMRU4gPSBNQVggLyAyOwoJTXlEaXJlY3QgZGlyZWN0OwoKCVJhbmRvbSBybmQ7CgoJaW50W10gZHggPSB7LTEsMCwxLDB9OwoJaW50W10gZHkgPSB7MCwtMSwwLDF9OwoKCXB1YmxpYyBSYW5kb21NYXplKCkgewoJCS8vIFRPRE8g6Ieq5YuV55Sf5oiQ44GV44KM44Gf44Kz44Oz44K544OI44Op44Kv44K/44O844O744K544K/44OWCgkJbWFwID0gbmV3IGJvb2xlYW5bTUFYKzJdW01BWCsyXVs0XTsKCQlhcnJvdyA9IG5ldyBpbnRbTUFYKzJdW01BWCsyXTsKCQlmb3IgKGludFtdIGEgOiBhcnJvdykgZmlsbChhLCAtMSk7CgkJZm9yIChpbnQgaT0wO2k8TUFYKzI7aSsrKSB7CgkJCW1hcFtpXVsxXVswXSAgID0gbWFwW2ldWzBdWzJdICAgICA9IG1hcFsxXVtpXVsxXSAgID0gbWFwWzBdW2ldWzNdICAgICA9IHRydWU7CgkJCW1hcFtpXVtNQVhdWzJdID0gbWFwW2ldW01BWCsxXVswXSA9IG1hcFtNQVhdW2ldWzNdID0gbWFwW01BWCsxXVtpXVsxXSA9IHRydWU7CgkJCWFycm93W2ldWzBdID0gYXJyb3dbaV1bTUFYKzFdID0gMTsgYXJyb3dbMF1baV0gPSBhcnJvd1tNQVgrMV1baV0gPSAwOwoJCX0KCgkJcm91dGUgPSBuZXcgTGlua2VkTGlzdDxpbnRbXT4oKTsKCQlyb3V0ZV9oID0gbmV3IEhhc2hTZXQ8UD4oKTsKCQl1c2VkID0gbmV3IEhhc2hTZXQ8UD4oKTsKCQlkaXJlY3QgPSBuZXcgTXlEaXJlY3QoKTsKCQlybmQgPSBuZXcgUmFuZG9tKFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpKTsKCi8vCQlwcmludF9ib2FyZCgpOwoJCWNyZWF0ZV9yb3V0ZSgpOwovLwkJcHJpbnRfYm9hcmQoKTsKCQl3aGlsZSAoISBpc19maW5pc2goKSkgewoJCQlQW10gcHV0cyA9IG5leHRfcHV0cygpOwoJCQlpbnQgciA9IHJuZC5uZXh0SW50KHB1dHMubGVuZ3RoKTsKCQkJY3JlYXRlX2JyYW5jaChwdXRzW3JdLngsIHB1dHNbcl0ueSwgcHV0c1tyXS5kKTsKCQl9CgoJCXByaW50X2JvYXJkKCk7Cgl9CgoJUFtdIG5leHRfcHV0cygpIHsKCQlBcnJheUxpc3Q8UD4gcHV0cyA9IG5ldyBBcnJheUxpc3Q8UD4oKTsKCQlmb3IgKGludCB5PTE7eTw9TUFYO3krKykgZm9yIChpbnQgeD0xO3g8PU1BWDt4KyspIHsKCQkJaWYgKGFycm93W3ldW3hdID49IDApIGNvbnRpbnVlOwoJCQlmb3IgKGludCBpPTA7aTw0O2krKyl7CgkJCQlpZiAobWFwW3ldW3hdW2ldKSBjb250aW51ZTsKCQkJCWlmIChhcnJvd1t5K2R5W2ldXVt4K2R4W2ldXSA8IDApIGNvbnRpbnVlOwoJCQkJcHV0cy5hZGQobmV3IFAoeCwgeSwgKGkrMiklNCkpOwoJCQkJYnJlYWs7CgkJCX0KCQl9CgkJcmV0dXJuIHB1dHMudG9BcnJheShuZXcgUFtde30pOwoJfQoKCXB1YmxpYyB2b2lkIGNyZWF0ZV9yb3V0ZSgpIHsKCQlpbnQgeCA9IHN4LCB5ID0gc3ksIGQgPSAtMTsKCQl3aGlsZSAoeCAhPSBleCB8fCB5ICE9IGV5KSB7CgkJCWludCBuZCA9IG5leHQoeCwgeSwgZCwgZGlyZWN0KTsKLy8JCQlkZWJ1Zyh4LCB5LCBkKTsKCQkJaWYgKG5kIDwgMCkgewoJCQkJdXNlZC5hZGQobmV3IFAoeCwgeSkpOwoJCQkJYXJyb3dbeV1beF0gPSAwOwoJCQkJaW50W10gdW5kbyA9IHJvdXRlLnJlbW92ZUxhc3QoKTsKCQkJCWludCBweCA9IHVuZG9bMF0sIHB5ID0gdW5kb1sxXSwgcGQgPSB1bmRvWzJdOwoJCQkJeCA9IHB4OyB5ID0gcHk7IGQgPSBwZDsKCgkJCQlpZiAocm91dGVfaC5yZW1vdmUobmV3IFAoeCwgeSkpKSB7Ci8vCQkJCQlkZWJ1Zygib2siKTsKLy8JCQkJCW5ldyBTY2FubmVyKFN5c3RlbS5pbikubmV4dCgpOwovLwkJCQkJcHJpbnRfYm9hcmQoKTsKCQkJCX0KCQkJCWNvbnRpbnVlOwoJCQl9CgoJCQlyb3V0ZS5hZGQobmV3IGludFtde3gsIHksIGR9KTsKCQkJZCA9IG5kOwoJCQlhcnJvd1t5XVt4XSA9IGQ7CgkJCXJvdXRlX2guYWRkKG5ldyBQKHgsIHkpKTsKCQkJdXNlZC5hZGQobmV3IFAoeCwgeSkpOwoKCQkJeCArPSBkeFtkXTsgeSArPSBkeVtkXTsKCQkJY3JlYXRlX3dhbGwoeCwgeSwgZCk7CgkJfQoJCXJvdXRlLmFkZChuZXcgaW50W117ZXgsIGV5LCAyfSk7CgkJcm91dGVfaC5hZGQobmV3IFAoZXgsIGV5KSk7CgkJdXNlZC5hZGQobmV3IFAoZXgsIGV5KSk7Cgl9CgoJcHJpdmF0ZSBib29sZWFuIG9uX3JvdXRlKGludCB4LCBpbnQgeSkgewoJCXJldHVybiByb3V0ZV9oLmNvbnRhaW5zKG5ldyBQKHgsIHkpKTsKCX0KCglwcml2YXRlIGJvb2xlYW4gdXNlZChpbnQgeCwgaW50IHkpIHsKCQlyZXR1cm4gdXNlZC5jb250YWlucyhuZXcgUCh4LCB5KSk7Cgl9CgoJcHVibGljIHZvaWQgY3JlYXRlX2JyYW5jaChpbnQgY3gsIGludCBjeSwgaW50IGNkKSB7CgkJaW50IHggPSBjeCwgeSA9IGN5LCBkID0gY2Q7CgkJQnJhbmNoIGJyYW5jaCA9IG5ldyBCcmFuY2goKTsKCQlmb3IoaW50IGNudCA9IDA7Y250IDwgTEVOO2NudCsrKSB7CgkJCXVzZWQuYWRkKG5ldyBQKHgsIHkpKTsKCQkJYXJyb3dbeV1beF0gPSBkOwoJCQljcmVhdGVfd2FsbCh4LCB5LCBkKTsKCQkJaW50IG5kID0gbmV4dCh4LCB5LCBkLCBicmFuY2gpOwoJCQlpZiAobmQgPCAwKSByZXR1cm47CgkJCWludCBueCA9IHggKyBkeFtuZF0sIG55ID0geSArIGR5W25kXTsKCQkJeCA9IG54OyB5ID0gbnk7IGQgPSBuZDsKCQl9Cgl9CgoJcHJpdmF0ZSBpbnQgbmV4dChpbnQgeCwgaW50IHksIGludCBkLCBEaXJlY3QgZGlyZWN0KSB7CgkJYm9vbGVhbltdIGYgPSBuZXcgYm9vbGVhbls0XTsKCgkJZm9yIChpbnQgaT0wO2k8NDtpKyspIHsKCQkJaWYgKGkgPT0gKGQrMiklNCkgewoJCQkJZltpXSA9IHRydWU7CgkJCQljb250aW51ZTsKCQkJfQoJCQlpZiAoYXJyb3dbeStkeVtpXV1beCtkeFtpXV0gPj0gMCkgewoJCQkJZltpXSA9IHRydWU7CgkJCQlpbnQgYXJyID0gYXJyb3dbeStkeVtpXV1beCtkeFtpXV07CgkJCQlmW2Fycl0gPSB0cnVlOwoJCQl9CgkJfQoKCQlpZiAoZlswXSAmIGZbMV0gJiBmWzJdICYgZlszXSkgcmV0dXJuIC0xOwoKCQlpbnQgZGlyOwoJCWRvIHsKCQkJZGlyID0gZGlyZWN0LmRpcmVjdCh4LCB5KTsKCQl9IHdoaWxlKGZbZGlyXSk7Ci8vCQlwcmludF9ib2FyZCgpOwoJCXJldHVybiBkaXI7Cgl9CgoJcHJpdmF0ZSB2b2lkIGNyZWF0ZV93YWxsKGludCB4LCBpbnQgeSwgaW50IGQpIHsKCQlmb3IgKGludCBpPTA7aTw0O2krKykgaWYoaSAhPSAoZCsyKSU0KSB7CgkJCW1hcFt5XVt4XVtpXSA9IG1hcFt5K2R5W2ldXVt4K2R4W2ldXVsoaSsyKSU0XSB8PSB1c2VkKHgrZHhbaV0sIHkrZHlbaV0pOwoJCX0KCX0KCglwcml2YXRlIGJvb2xlYW4gaXNfZmluaXNoKCkgewoJCXJldHVybiB1c2VkLnNpemUoKSA9PSBNQVggKiBNQVg7Cgl9CgoJcHVibGljIHZvaWQgcHJpbnRfYm9hcmQoKSB7CgkJZm9yIChpbnQgaT0wO2k8TUFYKjIrMTtpKyspIHsKCQkJaW50IHkgPSBpIC8gMiArIDE7CgkJCWlmIChpICUgMiA9PSAwKSB7CgkJCQlmb3IgKGludCB4PTE7eDw9TUFYO3grKykgewoJCQkJCVN5c3RlbS5vdXQucHJpbnQoIiAiKTsKCQkJCQlpZiAobWFwW3ldW3hdWzFdKSBTeXN0ZW0ub3V0LnByaW50KCItIik7CgkJCQkJZWxzZSBTeXN0ZW0ub3V0LnByaW50KCIgIik7CgkJCQl9CgkJCQlTeXN0ZW0ub3V0LnByaW50bG4oKTsKCQkJfSBlbHNlIHsKCQkJCWZvciAoaW50IHg9MTt4PD1NQVgrMTt4KyspIHsKCQkJCQlpZiAobWFwW3ldW3hdWzBdKSBTeXN0ZW0ub3V0LnByaW50KCJ8Iik7CgkJCQkJZWxzZSBTeXN0ZW0ub3V0LnByaW50KCIgIik7CgkJCQkJaWYgKHggPT0gTUFYKzEpIGJyZWFrOwoJCQkJCWlmIChzeCA9PSB4ICYmIHN5ID09IHkpIFN5c3RlbS5vdXQucHJpbnQoIiMiKTsKCQkJCQllbHNlIGlmIChleCA9PSB4ICYmIGV5ID09IHkpIFN5c3RlbS5vdXQucHJpbnQoIioiKTsKCQkJCQllbHNlIGlmIChvbl9yb3V0ZSh4LCB5KSkgU3lzdGVtLm91dC5wcmludCgibyIpOwoJCQkJCWVsc2UgaWYgKHVzZWQoeCwgeSkpIFN5c3RlbS5vdXQucHJpbnQoIiAiKTsKCQkJCQllbHNlIFN5c3RlbS5vdXQucHJpbnQoIiAiKTsKCQkJCX0KCQkJCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJCQl9CgkJfQoKCQlTeXN0ZW0ub3V0LnByaW50bG4oKTsKCX0KCgljbGFzcyBQIHsKCQlpbnQgeCwgeSwgZDsKCQlQKGludCB4LCBpbnQgeSkgewoJCQl0aGlzLnggPSB4OwoJCQl0aGlzLnkgPSB5OwoJCQlkID0gMDsKCQl9CgkJUChpbnQgeCwgaW50IHksIGludCBkKSB7CgkJCXRoaXMueCA9IHg7CgkJCXRoaXMueSA9IHk7CgkJCXRoaXMuZCA9IGQ7CgkJfQoKCQlwdWJsaWMgaW50IGhhc2hDb2RlKCkgewoJCQlyZXR1cm4geCAqIE1BWCArIHk7CgkJfQoKCQlwdWJsaWMgYm9vbGVhbiBlcXVhbHMoT2JqZWN0IG8pIHsKCQkJaWYgKG8gaW5zdGFuY2VvZiBQKSB7CgkJCQlQIHAgPSAoUCkgbzsKCQkJCXJldHVybiB4ID09IHAueCAmJiB5ID09IHAueTsKCQkJfQoJCQlyZXR1cm4gZmFsc2U7CgkJfQoJfQoKCWludGVyZmFjZSBEaXJlY3QgewoJCWludCBkaXJlY3QoaW50IHgsIGludCB5KTsKCX0KCgljbGFzcyBNeURpcmVjdCBpbXBsZW1lbnRzIERpcmVjdHsKCQlkb3VibGVbXVtdIHdhaWdodHMgPSB7CgkJCQl7MC40MCwgMC41MCwgMC45MCwgMS4wfSwKCQkJCXswLjQ1LCAwLjUwLCAwLjU1LCAxLjB9LAoJCQkJezAuMDUsIDAuNTAsIDAuOTUsIDEuMH0sCgkJCQl7MC40NSwgMC41MCwgMC41NSwgMS4wfSwKCQkJCXswLjE1LCAwLjMwLCAwLjY1LCAxLjB9CgkJfTsKCQlpbnRbXSB3YWlnaHRfZDsKCQlpbnQgZGl2OwoJCVJhbmRvbSBybmQ7CgoJCXB1YmxpYyBNeURpcmVjdCgpIHsKCQkJcm5kID0gbmV3IFJhbmRvbShTeXN0ZW0uY3VycmVudFRpbWVNaWxsaXMoKSk7CgkJCXdhaWdodF9kID0gbmV3IGludFt3YWlnaHRzLmxlbmd0aCArIDFdOwoJCQlkaXYgPSAoMiAqIE1BWCAvIHdhaWdodHMubGVuZ3RoKTsKCQkJZm9yIChpbnQgaT0xO2k8PXdhaWdodHMubGVuZ3RoO2krKykgewoJCQkJd2FpZ2h0X2RbaV0gPSBkaXYgKiBpOwoJCQl9CgkJfQoJCXB1YmxpYyBpbnQgZGlyZWN0KGludCB4LCBpbnQgeSkgewoJCQkvLyBUT0RPIOiHquWLleeUn+aIkOOBleOCjOOBn+ODoeOCveODg+ODieODu+OCueOCv+ODlgoJCQlkb3VibGUgciA9IHJuZC5uZXh0RG91YmxlKCk7CgkJCWludCBhcmVhID0gKHggKyB5KSAvIGRpdjsKCQkJZm9yIChpbnQgaT0wOztpKyspIGlmIChyIDwgd2FpZ2h0c1thcmVhXVtpXSl7CgkJCQlyZXR1cm4gaTsKCQkJfQoJCX0KCX0KCWNsYXNzIEJyYW5jaCBpbXBsZW1lbnRzIERpcmVjdHsKCQlSYW5kb20gcm5kOwoJCXB1YmxpYyBCcmFuY2goKSB7CgkJCS8vIFRPRE8g6Ieq5YuV55Sf5oiQ44GV44KM44Gf44Kz44Oz44K544OI44Op44Kv44K/44O844O744K544K/44OWCgkJCXJuZCA9IG5ldyBSYW5kb20oU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCkpOwoJCX0KCQlwdWJsaWMgaW50IGRpcmVjdChpbnQgeCwgaW50IHkpIHsKCQkJLy8gVE9ETyDoh6rli5XnlJ/miJDjgZXjgozjgZ/jg6Hjgr3jg4Pjg4njg7vjgrnjgr/jg5YKCQkJcmV0dXJuIHJuZC5uZXh0SW50KDQpOwoJCX0KCgl9CgoJdm9pZCBkZWJ1ZyhPYmplY3QuLi4gb3MpIHsKCQlTeXN0ZW0ub3V0LnByaW50bG4oQXJyYXlzLmRlZXBUb1N0cmluZyhvcykpOwoJfQoKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCQluZXcgUmFuZG9tTWF6ZSgpOwoJfQp9CgoK