fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Az9ZAL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!