Advertisement
chang2394

Untitled

Oct 24th, 2014
415
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. #define mp make_pair
  5. using namespace std;
  6.  
  7. typedef pair<int,int> pii;
  8. typedef pair<int,pii> piii;
  9.  
  10. const int inf = 11234567;
  11.  
  12. int dx[] = {1,-1,0,0};
  13. int dy[] = {0,0,1,-1};
  14. const int NN = 1123;
  15.  
  16. string ch[NN];
  17. int d[NN][NN];
  18.  
  19. pii st,en;
  20. int n,m,v;
  21.  
  22. bool pt(int x,int y){
  23.     if (x >= n or y >= m or x < 0 or y < 0) return false;
  24.     return true;
  25. }
  26.  
  27. bool valid(){
  28.     priority_queue<piii,vector<piii>,greater<piii> > pq;
  29.     pq.push(mp(0,st));
  30.     d[st.x][st.y] = 0;
  31.  
  32.     while(!pq.empty()){
  33.         pii cur = pq.top().y;
  34.         int dist = pq.top().x;
  35.         pq.pop();
  36.  
  37.         if (cur == en) return true;
  38.         if (d[cur.x][cur.y] < dist) continue;
  39.  
  40.         for(int i = 0; i < 4; ++i){
  41.             int xx = cur.x + dx[i];
  42.             int yy = cur.y + dy[i];
  43.  
  44.             if (!pt(xx,yy)) continue;
  45.             int dd = d[cur.x][cur.y] + 1;
  46.             if (dd > v) continue;
  47.  
  48.             if (ch[xx][yy] == 'F') dd = 0;
  49.             if (d[xx][yy] > dd){
  50.                 d[xx][yy] = dd;
  51.                 pq.push(mp(dd,mp(xx,yy)));
  52.             }
  53.         }
  54.     }
  55.     return false;
  56. }
  57.  
  58. void solve(){
  59.     cin >> n >> m >> v;
  60.     cin >> st.x >> st.y >> en.x >> en.y;
  61.  
  62.     st.x--,st.y--,en.x--,en.y--;
  63.     for(int i = 0; i < n; ++i){
  64.         cin >> ch[i];
  65.         for(int j = 0; j < m; ++j)
  66.             d[i][j] = inf;
  67.     }
  68.  
  69.     if (valid()) cout << "Hello, Deimos!\n";
  70.     else cout << "Dire victory\n";
  71. }
  72.  
  73. int main()
  74. {
  75.     ios_base::sync_with_stdio(0);
  76.     solve();
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement