Advertisement
Malinovsky239

Untitled

Oct 26th, 2011
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5.  
  6. #define N 1005
  7. #define y1 Y1
  8.  
  9. using namespace std;
  10.  
  11. int dist1[N][N], dist2[N][N], qx[N * N], qy[N * N], l, r, x, y, x1, y1, x2, y2;
  12. char a[N][N];
  13. bool start = false;
  14.  
  15. void add(int x, int y) {
  16.     qx[r] = x;
  17.     qy[r++] = y;
  18. }
  19.  
  20. int main() {
  21.     freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23.  
  24.     int n, m;
  25.     scanf("%d %d ", &n, &m);
  26.  
  27.     memset(dist1, 127, sizeof(dist1));
  28.     memset(dist2, 127, sizeof(dist2));
  29.  
  30.     for (int i = 0; i < n; i++)
  31.         for (int j = 0; j < m; j++) {
  32.             cin >> a[i][j];
  33.             if (a[i][j] == 'T')
  34.                 x2 = i, y2 = j, a[i][j] = '.';
  35.             if (a[i][j] == '.' && !start) {
  36.                 start = true;
  37.                 x = i, y = j;
  38.             }
  39.             if (a[i][j] == '.')
  40.                 x1 = i, y1 = j;
  41.         }
  42.  
  43.     add(x, y);
  44.     dist1[x][y] = 0;
  45.     while (l < r) {
  46.         int nowx = qx[l], nowy = qy[l++];
  47.  
  48.         for (int dx = -1; dx < 2; dx++)
  49.             for (int dy = -1; dy < 2; dy++)
  50.                 if (abs(dx) + abs(dy) == 1) {
  51.                     if (a[nowx + dx][nowy + dy] == '.') {
  52.                         if (dist1[nowx + dx][nowy + dy] > dist1[nowx][nowy] + 1) {
  53.                             dist1[nowx + dx][nowy + dy] = dist1[nowx][nowy] + 1;
  54.                             add(nowx + dx, nowy + dy);                                                                                                                                                                     
  55.                         }                      
  56.                     }
  57.                 }
  58.     }
  59.  
  60.     l = r = 0;
  61.     add(x2, y2);
  62.     dist2[x2][y2] = 0;
  63.     while (l < r) {
  64.         int nowx = qx[l], nowy = qy[l++];
  65.  
  66.         for (int dx = -1; dx < 2; dx++)
  67.             for (int dy = -1; dy < 2; dy++)
  68.                 if (abs(dx) + abs(dy) == 1) {
  69.                     if (a[nowx + dx][nowy + dy] == '.') {
  70.                         if (dist2[nowx + dx][nowy + dy] > dist2[nowx][nowy] + 1) {
  71.                             dist2[nowx + dx][nowy + dy] = dist2[nowx][nowy] + 1;
  72.                             add(nowx + dx, nowy + dy);                                                                                                                                                                     
  73.                         }                      
  74.                     }
  75.                 }
  76.     }
  77.  
  78.     if (dist1[x1][y1] < dist2[x1][y1])
  79.         puts("Yes");               
  80.     else
  81.         puts("No");    
  82.  
  83.     return 0;
  84. }
  85.  
  86.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement