chang2394

Untitled

Oct 24th, 2014
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.41 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8. #include <stack>
  9. #include <cstring>
  10. #include <cmath>
  11. #include <climits>
  12. #include <sstream>
  13. #include <numeric>
  14. #include <iomanip>
  15.  
  16. #define pb push_back
  17. #define ill long long int
  18. #define ull unsigned long long int
  19. #define pii pair<int,int>
  20. #define s(n) scanf("%d", &n)
  21. #define gc getchar_unlocked
  22. #define ss(n) scanf("%s", n)
  23. #define sl(n) scanf("%lld", &n)
  24. #define pb push_back
  25. #define F(i,a,b) for(int i=(a); i<(b); i++)
  26. #define mem(a, v) memset(a, v, sizeof(a))
  27. #define all(v) v.begin(),v.end()
  28. #define fr first
  29. #define sc second
  30. #define mp make_pair
  31. #define deb cout <<"coink" <<endl
  32. #define mod 1000000007
  33. #define MAX 500100
  34. #define inf (int)1e9
  35. #define sq(x) ((x)*(x))
  36. #define sqrtsum(x, y) sqrt((x)*(x)+(y)*(y))
  37. #define abs(x) (x>0?x:-(x))
  38. #define prin(v) forall(i, 0, v.size()) cout << v[i] <<" ";cout <<endl;
  39. #define input freopen("in","r", stdin)
  40. #define output freopen("out","w", stdout)
  41. #define iost ios_base::sync_with_stdio(false)
  42. using namespace std;
  43.  
  44. int dx[] = {1, -1, 0, 0};
  45. int dy[] = {0, 0, -1 ,1};
  46. void swap(int &a, int &b) {int t = a;a = b;b = t;}
  47. int n, m, sx, sy, ddx, ddy, kk;
  48. vector<string> v;
  49. int vis[1100][1100];
  50. int dis[1100][1100];
  51. #define pip pair<int, pii>
  52. bool check() {
  53.  
  54.     priority_queue< pip , vector<pip >, greater<pip> > q;
  55.     q.push(mp(0, mp(sx, sy)));
  56.     F(i, 0,n) F(j, 0,m) dis[i][j] = inf;
  57.     mem(vis,0);
  58.     while(!q.empty()) {
  59.         pair<int, pii > u = q.top();
  60.         // cout << "cost" <<u.fr <<" " <<u.sc.fr <<" " << u.sc.sc <<" " << ddx <<" " << ddy <<endl;
  61.         q.pop();
  62.         if(u.sc.fr == ddx && u.sc.sc == ddy) return true;;
  63.         if(u.fr >= kk) continue;
  64.        
  65.         if(v[u.sc.fr][u.sc.sc] == 'F') {
  66.             if(vis[u.sc.fr][u.sc.sc]) continue;
  67.             vis[u.sc.fr][u.sc.sc] = 1;
  68.             // cout << "cost" <<u.fr <<" " <<u.sc.fr <<" " << u.sc.sc <<" " << ddx <<" " << ddy <<endl;
  69.             F(i, 0, 4) {
  70.                 int x = u.sc.fr+dx[i];
  71.                 int y = u.sc.sc+dy[i];
  72.                 if(x <0 || y < 0 || x >= n || y >= m) continue;
  73.                 if(vis[x][y]) continue;
  74.                 if(v[x][y] == '.') {
  75.                     q.push(mp(1, mp(x, y)));
  76.                 } else {
  77.                     q.push(mp(0, mp(x, y)));
  78.                 }
  79.             }
  80.            
  81.         } else {
  82.             if(dis[u.sc.fr][u.sc.sc] <= u.fr) continue;
  83.             // cout << "cost" <<u.fr <<" " <<u.sc.fr <<" " << u.sc.sc <<" " << ddx <<" " << ddy <<endl;
  84.             dis[u.sc.fr][u.sc.sc] = u.fr;
  85.            
  86.             F(i, 0, 4) {
  87.                 int x = u.sc.fr+dx[i];
  88.                 int y = u.sc.sc+dy[i];
  89.                 if(x <0 || y < 0 || x >= n || y >= m) continue;
  90.                 if(vis[x][y]) continue;
  91.                 if(v[x][y] == '.') {
  92.                     q.push(mp(u.fr+1, mp(x, y)));
  93.                 } else {
  94.                     q.push(mp(0, mp(x, y)));
  95.                 }
  96.             }
  97.         }
  98.  
  99.     }
  100.    
  101.     return false;
  102. }
  103. int main(){
  104.     // input;
  105.     cin >> n >> m>> kk;
  106.     cin >> sx >> sy >> ddx >> ddy;
  107.     sx--;   sy--;   ddx--;  ddy--;
  108.     v.resize(n);
  109.     F(i, 0,n)
  110.     cin >> v[i];
  111.    
  112.    
  113.     if(check()) {
  114.         cout << "Hello, Deimos!" <<endl;
  115.         return 0;
  116.     }
  117.     cout <<"Dire victory" <<endl;
  118.     return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment