Advertisement
Josif_tepe

Untitled

Mar 16th, 2023
723
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <fstream>
  7. using namespace std;
  8. const int maxn = 2222;
  9. char mat[maxn][maxn];
  10. int main() {
  11.     ios_base::sync_with_stdio(false);
  12.     int n, m, si, sj, L, R;
  13.     cin >> n >> m;
  14.     cin >> si >> sj;
  15.     cin >> L >> R;
  16.    
  17.     si--; sj--;
  18.     for(int i = 0; i < n; i++) {
  19.         for(int j = 0; j < m; j++) {
  20.             cin >> mat[i][j];
  21.         }
  22.     }
  23.     vector<vector<int> > dist(n + 1, vector<int>(m + 1, 2e9));
  24.     vector<vector<bool> > visited(n + 1, vector<bool>(m + 1, false));
  25.    
  26.     dist[si][sj] = 0;
  27.     deque<pair<int, int> > dq;
  28.     dq.push_back(make_pair(si, sj));
  29.    
  30.     int di[] = {-1, 1, 0, 0};
  31.     int dj[] = {0, 0, 1, -1};
  32.     while(!dq.empty()) {
  33.         int ci = dq.front().first;
  34.         int cj = dq.front().second;
  35.         dq.pop_front();
  36.        
  37.         if(!visited[ci][cj]) {
  38.             visited[ci][cj] = true;
  39.            
  40.             for(int i = 0; i < 4; i++) {
  41.                 int ti = ci + di[i];
  42.                 int tj = cj + dj[i];
  43.                 if(ti >= 0 and ti < n and tj >= 0 and tj < m and mat[ti][tj] != '*') {
  44.                     int cost = 0;
  45.                    
  46.                     if(i == 3) {
  47.                         cost = 1;
  48.                     }
  49.                    
  50.                     if(dist[ci][cj] + cost < dist[ti][tj]) {
  51.                         dist[ti][tj] = dist[ci][cj] + cost;
  52.                         if(cost == 0) {
  53.                             dq.push_front(make_pair(ti, tj));
  54.                         }
  55.                         else {
  56.                             dq.push_back(make_pair(ti, tj));
  57.                         }
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.     }
  63.     int result = 0;
  64.     for(int i = 0; i < n; i++) {
  65.         for(int j = 0; j < m; j++) {
  66.             if(dist[i][j] < 2e9) {
  67.                 int l_tmp = dist[i][j];
  68.                 int r_tmp = j - sj + l_tmp;
  69.                 if(l_tmp <= L and r_tmp <= R) {
  70.                     result++;
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     cout << result << endl;
  76.     return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement