留个纪念吧

  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