留个纪念吧
1 import java.io.*;
2 import java.util.*;
3
4 /*
5 LANG: JAVA
6 TASK: maze1
7 */
8 public class maze1 {
9
10 /**
11 * @param args
12 * @throws IOException
13 */
14 public static void main(String[] args) throws IOException {
15 // TODO Auto-generated method stub
16 BufferedReader f = new BufferedReader(new FileReader("maze1.in"));
17 PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("maze1.out")));
18
19 StringTokenizer st = new StringTokenizer(f.readLine());
20 int W = Integer.parseInt(st.nextToken());
21 int H = Integer.parseInt(st.nextToken());
22
23 char[][] maze = new char[2 * H + 1][2 * W + 1];
24
25 for (int i = 0; i < 2 * H + 1; i++)
26 {
27 String temp = f.readLine();
28 maze[i] = temp.toCharArray();
29 }
30
31 byte[][] D = new byte[W*H][W*H];
32
33 for (int i = 0; i < W * H; i++)
34 for (int j = 0; j < W * H; j++)
35 {
36 if (i!=j)
37 D[i][j] = -1;
38 else
39 D[i][j] = 0;
40 }
41
42 for (int i = 0; i < H; i++)
43 for (int j = 0; j < W; j++)
44 {
45 int x = 1 + 2 * j;
46 int y = 1 + 2 * i;
47 int current = i * W + j;
48
49 if (i - 1 >= 0)
50 {
51 if (maze[y - 1][x] != '-')
52 {
53 D[(i - 1) * W + j][current] = 1;
54 D[current][(i - 1) * W + j] = 1;
55 }
56 }
57
58 if (i + 1 < H)
59 {
60 if (maze[y + 1][x] != '-')
61 {
62 D[(i + 1) * W + j][current] = 1;
63 D[current][(i + 1) * W + j] = 1;
64 }
65 }
66
67 if (j - 1 >= 0)
68 {
69 if (maze[y][x - 1] != '|')
70 {
71 D[i * W + j - 1][current] = 1;
72 D[current][i * W + j - 1] = 1;
73 }
74 }
75
76 if (j + 1 < W)
77 {
78 if (maze[y][x + 1] != '|')
79 {
80 D[i * W + j + 1][current] = 1;
81 D[current][i * W + j + 1] = 1;
82 }
83 }
84
85 }
86
87 int exit1 = -1;
88 int exit2 = -1;
89
90 for (int i = 0; i < W; i++)
91 {
92 int x = 1 + 2 * i;
93 int y1 = 0;
94 int y2 = 2 * H;
95
96 if (maze[y1][x] != '-')
97 {
98 if (exit1 == -1)
99 exit1 = i;
100 else
101 exit2 = i;
102 }
103 if (maze[y2][x] != '-')
104 {
105 if (exit1 == -1)
106 exit1 = W * (H - 1) + i;
107 else
108 exit2 = W * (H - 1) + i;
109 }
110 }
111
112 for (int j = 0; j < H; j++)
113 {
114 int y = 1 + 2 * j;
115 int x1 = 0;
116 int x2 = 2 * W;
117
118 if (maze[y][x1] != '|')
119 {
120 if (exit1 == -1)
121 exit1 = j * W;
122 else
123 exit2 = j * W;
124 }
125
126 if (maze[y][x2] != '|')
127 {
128 if (exit1 == -1)
129 exit1 = j * W + W - 1;
130 else
131 exit2 = j * W + W - 1;
132 }
133 }
134
135
136
137 int max = -1;
138
139
140 int[] distance = new int[H * W];
141 boolean[] visited = new boolean[H * W];
142
143 int[] distance1 = new int[H * W];
144 boolean[] visited1 = new boolean[H * W];
145
146 for (int i = 0; i < H * W; i++)
147 {
148 if (D[exit1][i]!=-1)
149 distance[i] = D[exit1][i];
150 else
151 distance[i] = 100000;
152
153 if (D[exit2][i]!=-1)
154 distance1[i] = D[exit2][i];
155 else
156 distance1[i] = 100000;
157 }
158
159
160 visited1[exit2] = true;
161
162 visited[exit1] = true;
163
164 int nodevisited = 1;
165
166 while (nodevisited < H * W - 1)
167 {
168 int min = 1000000;
169 int i = 0;
170 for (int j = 0; j < H * W; j++)
171 {
172 if (visited[j] == false)
173 {
174 if (j!=exit1 && distance[j] < min)
175 {
176 min = distance[j];
177 i = j;
178 }
179
180 }
181 }
182 visited[i] = true;
183 nodevisited++;
184
185 for (int j = 0; j < H * W; j++)
186 if (j != i && D[j][i] != -1)
187 {
188 if (distance[i] + D[i][j] < distance[j])
189 distance[j] = distance[i] + D[i][j];
190
191 }
192 }
193
194
195 nodevisited = 1;
196 while (nodevisited < H * W - 1)
197 {
198 int min = 1000000;
199 int i = 0;
200 for (int j = 0; j < H * W; j++)
201 {
202 if (visited1[j] == false)
203 {
204 if (j!=exit2 && distance1[j] < min)
205 {
206 min = distance1[j];
207 i = j;
208 }
209
210 }
211 }
212 visited1[i] = true;
213 nodevisited++;
214
215 for (int j = 0; j < H * W; j++)
216 if (j != i && D[j][i] != -1)
217 {
218 if (distance1[i] + D[i][j] < distance1[j])
219 distance1[j] = distance1[i] + D[i][j];
220
221 }
222 }
223
224
225
226
227
228
229 for (int i = 0; i < H * W; i++)
230 {
231 if (distance[i] > distance1[i])
232 {
233 if (distance1[i] > max)
234 max = distance1[i];
235 }
236 else
237 {
238 if (distance[i] > max)
239 max = distance[i];
240 }
241 }
242
243 out.println(max+1);
244 out.close();
245 System.exit(0);
246 }
247
248 }
249