Guest User

Untitled

a guest
Sep 23rd, 2014
641
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.51 KB | None | 0 0
  1. #include <cstring>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <numeric>
  13. #include <utility>
  14. #include <sstream>
  15. #include <iostream>
  16. #include <iomanip>
  17. #include <cstdio>
  18. #include <cmath>
  19. #include <cstdlib>
  20. #include <ctime>
  21. #include <memory.h>
  22. #include <cassert>
  23.  
  24. using namespace std;
  25.  
  26.  
  27. const int N = 22, NINF = -(1 << 30);
  28. char maze[N][N], res[][15] = { "IMPOSSIBLE", "SUCCESS" };
  29. int n, m, k, v[N][N], dist[N][N];
  30. int dx[] = { -1, 1, 0, 0 };
  31. int dy[] = { 0, 0, -1, 1 };
  32.  
  33. struct ii {
  34.     int x, y, s;
  35.     ii(void) {}
  36.     ii(int x, int y, int s) : x(x), y(y), s(s) {}
  37.     bool operator<(const ii &o) const {
  38.         if (s == o.s && x != o.x)
  39.             return x > o.x;
  40.         if (s == o.s && x == o.x)
  41.             return y > o.y;
  42.         return s < o.s;
  43.     }
  44. };
  45.  
  46. bool valid(int nx, int ny) {
  47.     return nx >= 0 && ny >= 0 && nx < n && ny < m;
  48. }
  49.  
  50. bool bfs(int x, int y) {
  51.     priority_queue <ii> pq; pq.push(ii(x, y, k));
  52.     dist[x][y] = k;
  53.     bool taken = false;
  54.     while (pq.size()) {
  55.         ii co = pq.top(); pq.pop();
  56.         int X = co.x, Y = co.y, S = co.s;
  57.         if (S < 0) continue;
  58.         for (int i = 0; i < 4; ++i) {
  59.             int nx = X + dx[i], ny = Y + dy[i];
  60.             if (valid(nx, ny) && maze[nx][ny] != '#') {
  61.                 if (maze[nx][ny] == '.') {
  62.                     if (nx == 1 && ny == 3)
  63.                         printf("that %d, %d\n", X, Y);
  64.                     if (dist[nx][ny] < dist[X][Y]) {
  65.                         dist[nx][ny] = dist[X][Y];
  66.                         pq.push(ii(nx, ny, dist[nx][ny]));
  67.                     }
  68.                 } else if (maze[nx][ny] == 's') {
  69.                     if (dist[nx][ny] < dist[X][Y] - 1 && dist[X][Y] - 1 >= 0) {
  70.                         dist[nx][ny] = dist[X][Y] - 1;
  71.                         pq.push(ii(nx, ny, dist[nx][ny]));
  72.                     }
  73.                 } else if (maze[nx][ny] == 'x') {
  74.                     if (k - dist[X][Y] <= dist[X][Y])
  75.                         return true;
  76.                     taken = true;
  77.                     //if (dist[X][Y] == 0) return false;
  78.                     if (dist[nx][ny] < dist[X][Y]) {
  79.                         dist[nx][ny] = dist[X][Y];
  80.                         pq.push(ii(nx, ny, dist[nx][ny]));
  81.                     }
  82.  
  83.                 } else if (maze[nx][ny] == '@' && taken) return true;
  84.             }
  85.         }
  86.     }
  87.     return false;
  88. }
  89.  
  90. int main(void) {
  91.     //freopen("in.txt", "r", stdin);
  92.     scanf("%d %d %d\n", &n, &m, &k);
  93.     int sx, sy, ex, ey, cn = 0;
  94.  
  95.     for (int i = 0; i < n; i++) {
  96.         scanf("%s", maze[i]);
  97.         for (int j = 0; j < m && cn < 2; j++) {
  98.             switch (maze[i][j]) {
  99.             case '@':
  100.                 sx = i, sy = j, ++cn;
  101.                 break;
  102.             case 'x':
  103.                 ex = i, ey = j, ++cn;
  104.                 break;
  105.             }
  106.         }
  107.     }
  108.     memset(dist, -1, sizeof dist);
  109.     printf("%s\n", res[bfs(sx, sy)]);
  110. }
Advertisement
Add Comment
Please, Sign In to add comment