Guest User

Untitled

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