fork download
  1. #include <bits/stdc++.h>
  2. #include<limits.h>
  3. #include<stdio.h>
  4. #include<cstring>
  5. #include<string>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef long double ld;
  9. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  10. #define pb push_back
  11. #define mp make_pair
  12. #define sz(a) a.size()
  13. #define fi first
  14. #define se second
  15. #define rsz(a,n) a.resize(n)
  16. #define test(t) ll t;cin>>t;while(t--)
  17. #define forn(i,e) for(int i = 0; i < e; i++)
  18. #define forsn(i,s,e) for(int i = s; i < e; i++)
  19. #define rforn(i,s) for(int i = s; i >= 0; i--)
  20. #define rforsn(i,s,e) for(int i = s; i >= e; i--)
  21. #define fillv(a,k) memset(a,k,sizeof(a))
  22. #define leadzero(a) __builtin_clz(a) //count leading zeros
  23. #define trailzero(a) __builtin_ctz(a) //count trailing zeros
  24. #define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
  25. #define ln cout<<"\n"
  26. #define sp cout<<" "
  27. #define spaceprint(a,i,s,n) {forsn(i,s,n) { cout<<a[i]; sp;}}
  28. #define lineprint(a,i,s,n) {forsn(i,s,n) {cout<<a[i]; ln;}}
  29. #define maxe(a) *max_element(a.begin(),a.end())
  30. #define maxi(a) max_element(a.begin(),a.end())-a.begin()
  31. #define mine(a) *min_element(a.begin(),a.end())
  32. #define mini(a) min_element(a.begin(),a.end())-a.begin()
  33. #define all(c) c.begin(),c.end()
  34. #define trav(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  35. #define present(container, element) (container.find(element) != container.end())
  36. #define cpresent(container, element) (find(all(container),element) != container.end())// check the presence of element
  37. //copy(from_begin, from_end, to_begin); copy function
  38. typedef unsigned long long int ull;
  39. typedef long double ld;
  40. typedef pair<ll,ll> p64;
  41. typedef pair<int,int> p32;
  42. typedef pair<int,p32> p96;
  43. typedef vector<ll> v64;
  44. typedef vector<string> vs;
  45. typedef vector<int> v32;
  46. typedef vector<v32> vv32;
  47. typedef vector<v64> vv64;
  48. typedef vector<p32> vp32;
  49. typedef vector<p64> vp64;
  50. typedef vector<vp32> vvp32;
  51. typedef map<int,int> m32;
  52. typedef map<ll,ll> m64;
  53. const int LIM = 1e5+5, MOD = 1e9+7;
  54. #define sumv(v) accumulate(all(v),ll(0))
  55. #define productv(v) accumulate(all(v), ll(1), multiplies< ll >())
  56. ll gcd(ll a, ll b) { if(b == 0) return a; return gcd(b, a % b); }
  57. ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }
  58. bool seive[2005];
  59. void SieveOfEratosthenes(ll n)
  60. { memset(seive, true, sizeof(seive)); for (ll p=2; p*p<=n; p++) if (seive[p] == true) for (ll i=p*p; i<=n; i += p) seive[i] = false; }
  61. ll fastpow(ll a, ll p){ if(p==0) return 1; ll z = fastpow(a,p/2); z = (z*z); if(p%2) z = (z*a); return z; }
  62. ll dx[]={1,-1,0,0};
  63. ll dy[]={0,0,1,-1};
  64. ll visited[2005][2005]={0};
  65. ll val[2005][2005];
  66. char a[2005][2005];
  67. ll l1,r1;
  68. ll x_total,y_total;
  69. priority_queue <pair<ll,pair<ll,ll>>> pq;
  70. int main()
  71. {
  72. // djikstra with 1 weight assigned to all the left moving edge(path) else all paths /edges have 0 weight
  73. fast;//fast i/o
  74. ll n,i,y_origin,x_origin;
  75. cin>>y_total>>x_total;//coordinates of the total cell structure
  76. cin>>y_origin>>x_origin;//coordintes of the orignal point
  77. cin>>l1>>r1;
  78. y_origin--;//co-ordinte substracted so that 0-cordinate system can be used;
  79. x_origin--;
  80. for(ll i=0;i<y_total;i++)
  81. for(ll j=0;j<x_total;j++)
  82. {
  83. cin>>a[i][j]; //character array
  84. val[i][j]=LLONG_MAX;//the shortest length to all paths to be infinity
  85. }
  86. pq.push(mp(0,mp(y_origin,x_origin)));//origin pushed to priority_queue
  87. val[y_origin][x_origin]=0;
  88. while(!pq.empty())
  89. {
  90. ll present_father_y=pq.top().se.fi;//present_coordinate
  91. ll present_father_x=pq.top().se.se;//present_coordinate
  92. ll present_father_val=-pq.top().fi;//present_value
  93. pq.pop();
  94. visited[present_father_y][present_father_x]=1;//array so that same co-ordinate is not visited
  95. for(ll k=0;k<4;k++)
  96. {
  97. ll child_y=present_father_y+dy[k];
  98. ll child_x=present_father_x+dx[k];
  99. if(child_x<0 or child_x>=x_total or child_y<0 or child_y>=y_total)//check the bounds
  100. continue;
  101. if(a[child_y][child_x]=='*')
  102. continue;
  103. if(visited[child_y][child_x])
  104. {
  105. continue;
  106. }
  107. ll child_val=present_father_val+(dx[k]==-1);
  108. if(child_val>l1)//if no of lefts is exceeded dont add it to queue(optimization)
  109. continue;
  110. if(val[child_y][child_x]>=child_val)
  111. {
  112. val[child_y][child_x]=child_val;
  113. pq.push(mp(-child_val,mp(child_y,child_x)));
  114. }
  115. }
  116. }
  117. ll sum=0;
  118. for(ll i=0;i<y_total;i++)
  119. for(ll j=0;j<x_total;j++)
  120. {
  121. if(visited[i][j]==0)
  122. continue;
  123. if(val[i][j]<=l1 and val[i][j]-x_origin+j<=r1)//final-check
  124. {
  125. sum++;
  126. }
  127. }
  128. cout<<sum;
  129.  
  130.  
  131.  
  132. }
  133.  
Runtime error #stdin #stdout 0s 81984KB
stdin
Standard input is empty
stdout
Standard output is empty