Advertisement
Guest User

Untitled

a guest
Jun 16th, 2012
296
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.20 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. import static java.lang.Math.*;
  4.  
  5. public class Labyrinth implements Runnable {
  6.    
  7.     final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
  8.    
  9.     BufferedReader in;
  10.     PrintWriter out;
  11.     StringTokenizer tok;
  12.    
  13.     @Override
  14.     public void run() {
  15.         try {
  16.             long startTime = System.currentTimeMillis();
  17.             if (ONLINE_JUDGE) {
  18.                 in = new BufferedReader(new InputStreamReader(System.in));
  19.                 out = new PrintWriter(System.out);
  20.             } else {
  21.                 in = new BufferedReader(new FileReader("input.txt"));
  22.                 out = new PrintWriter("output.txt");
  23.             }
  24.             tok = new StringTokenizer("");
  25.             Locale.setDefault(Locale.US);
  26.             solve();
  27.             in.close();
  28.             out.close();
  29.             long endTime = System.currentTimeMillis();
  30.             long totalMemory = Runtime.getRuntime().totalMemory();
  31.             long freeMemory = Runtime.getRuntime().freeMemory();
  32.             System.err.println("Time = " + (endTime - startTime) + " ms");
  33.             System.err.println("Memory = " + ((totalMemory - freeMemory) / 1024) + " KB");
  34.         } catch (Throwable e) {
  35.             e.printStackTrace(System.err);
  36.             System.exit(-1);
  37.         }
  38.     }
  39.    
  40.     String readString() throws IOException {
  41.         while (!tok.hasMoreTokens()) {
  42.             tok = new StringTokenizer(in.readLine());
  43.         }
  44.         return tok.nextToken();
  45.     }
  46.    
  47.     int readInt() throws IOException {
  48.         return Integer.parseInt(readString());
  49.     }
  50.    
  51.     long readLong() throws IOException {
  52.         return Long.parseLong(readString());
  53.     }
  54.    
  55.     double readDouble() throws IOException {
  56.         return Double.parseDouble(readString());
  57.     }
  58.    
  59.     void debug(Object... o) {
  60.         if (!ONLINE_JUDGE) {
  61.             System.err.println(Arrays.deepToString(o));
  62.         }
  63.     }
  64.    
  65.     public static void main(String[] args) {
  66.         new Thread(null, new Labyrinth(), "", 256 * 1024 * 1024).start();
  67.     }
  68.    
  69. //------------------------------------------------------------------------------
  70.    
  71.     final int[] dx = {0, 1, 0, -1};
  72.     final int[] dy = {-1, 0, 1, 0};
  73.    
  74.     int n, m;
  75.     char[][] a;
  76.     int[][] wx, wy;
  77.     boolean[][] vis;
  78.    
  79.     void solve() throws IOException {
  80.         n = readInt();
  81.         m = readInt();
  82.         a = new char[n][];
  83.         for (int i = 0; i < n; i++) {
  84.             a[i] = readString().toCharArray();
  85.         }
  86.         int sx = -1, sy = -1;
  87.         loop: for (int i = 0; i < n; i++) {
  88.             for (int j = 0; j < m; j++) {
  89.                 if (a[i][j] == 'S') {
  90.                     sx = i;
  91.                     sy = j;
  92.                     break loop;
  93.                 }
  94.             }
  95.         }
  96.         wx = new int[n][m];
  97.         wy = new int[n][m];
  98.         vis = new boolean[n][m];
  99.         if (dfs(sx, sy, 0, 0)) {
  100.             out.println("Yes");
  101.         } else {
  102.             out.println("No");
  103.         }
  104.     }
  105.  
  106.     private boolean dfs(int x, int y, int shiftX, int shiftY) {
  107.         if (vis[x][y]) {
  108.             if (wx[x][y] != shiftX || wy[x][y] != shiftY) {
  109.                 return true;
  110.             } else {
  111.                 return false;
  112.             }
  113.         }
  114.         vis[x][y] = true;
  115.         wx[x][y] = shiftX;
  116.         wy[x][y] = shiftY;
  117.         for (int k = 0; k < 4; k++) {
  118.             int newX = x + dx[k];
  119.             int newY = y + dy[k];
  120.             int newShiftX = shiftX;
  121.             int newShiftY = shiftY;
  122.             if (newX >= n) { newX = 0; newShiftX++; }
  123.             if (newY >= m) { newY = 0; newShiftY++; }
  124.             if (newX < 0) { newX = n-1; newShiftX--; }
  125.             if (newY < 0) { newY = m-1; newShiftY--; }
  126.             if (a[newX][newY] != '#') {
  127.                 if (dfs(newX, newY, newShiftX, newShiftY)) {
  128.                     return true;
  129.                 }
  130.             }
  131.         }
  132.         return false;
  133.     }
  134.    
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement