1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
|
/*
* Przemyslaw Horban (nr. albumu: 262940)
* Uniwersystet Warszawski
*/
package labrunner;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author Przemyslaw Horban <[email protected]>
*/
public class LabRunner {
char[][] map;
int w, h;
private int[] ox = {-1, 1, 0, 0},
oy = {0, 0, 1, -1};
private char[] stepChar = {'<', '>', 'v', '^'};
int dirCh;
private boolean walk(int x, int y) {
if(checkDeadEnds(x, y) && checkReachability(x, y)) {
boolean wayToGo = false;
for(int i = 0; i < 4; i++) {
int nx = x + ox[i],
ny = y + oy[i];
if(nx >= 0 && nx < w &&
ny >= 0 && ny < h &&
map[ny][nx] == '.') {
wayToGo = true;
map[y][x] = stepChar[i];
if(walk(nx, ny))
return true;
map[y][x] = '.';
}
}
if(!wayToGo)
return true;
}
return false;
}
private boolean checkDeadEnds(int x, int y) {
int deadEnds = 0;
for(int py = 0; py < h; py++)
for(int px = 0; px < w; px++) {
if(!(x == px && y == py) && map[py][px] == '.') {
int blockedWays = 4;
for(int i = 0; i < 4; i++) {
int newX = px + ox[i],
newY = py + oy[i];
if(newX >= 0 && newX < w &&
newY >= 0 && newY < h &&
map[newY][newX] == '.')
blockedWays--;
}
if(blockedWays == 4) return false;
if(blockedWays == 3) {
deadEnds++;
if(deadEnds > 1)
return false;
}
}
}
return true;
}
class Pt {
int x, y;
Pt(int x, int y) {
this.x = x;
this.y = y;
}
}
private boolean checkReachability(int x, int y) {
List<Pt> toVisit = new ArrayList<Pt>();
boolean[][] visited = new boolean[h][w];
toVisit.add(new Pt(x, y));
visited[y][x] = true;
while(!toVisit.isEmpty()) {
Pt p = toVisit.get(toVisit.size() - 1);
toVisit.remove(toVisit.size() - 1);
for(int i = 0; i < 4; i++) {
int newX = p.x + ox[i],
newY = p.y + oy[i];
if(newX >= 0 && newX < w &&
newY >= 0 && newY < h &&
map[newY][newX] == '.' &&
visited[newY][newX] == false) {
visited[newY][newX] = true;
toVisit.add(new Pt(newX, newY));
}
}
}
for(int py = 0; py < h; py++)
for(int px = 0; px < w; px++)
if(!visited[py][px] && map[py][px] == '.')
return false;
return true;
}
public String[] findPath(String[] lab) {
h = lab.length;
w = lab[0].length();
map = new char[h][w];
for(int py = 0; py < h; py++)
for(int px = 0; px < w; px++)
map[py][px] = lab[py].charAt(px);
int py=0, px=0;
boolean solutionExists = false;
outer:
for(py = 0; py < h; py++)
for(px = 0; px < w; px++)
if(map[py][px] == '.' && walk(px, py)) {
solutionExists = true;
break outer;
}
if(!solutionExists)
throw new RuntimeException("Puzzle has no solution!");
String[] ret = new String[h+1];
ret[0] = "Start at x="+px+" y="+py;
for(int y = 0; y < h; y++)
ret[y+1] = new String(map[y]);
return ret;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
LabRunner lr = new LabRunner();
String[] lab = {
".....x....",
".....x....",
".....x....",
"...xxxxx..",
".....x....",
".....x....",
".....x....",
"..x..x....",
"..x.......",
"..x.....xx",
"..x.....xx",
"..x.....xx",
"..x..x..xx",
"..x..x..xx"};
String[] sol = lr.findPath(lab);
for (int i = 0; i < sol.length; i++) {
System.out.println(sol[i]);
}
}
}
|
