fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. ///CHECKING @Tanvir
  4. #define ft first
  5. #define sd second
  6. #define pb push_back
  7. #define all(x) x.begin(),x.end()
  8.  
  9. #define ll long long int
  10. #define vi vector<int>
  11. #define vii vector<pair<int,int> >
  12. #define pii pair<int,int>
  13. #define piii pair<int, pii>
  14. #define mp make_pair
  15.  
  16.  
  17. #define f_in(st) freopen(st,"r",stdin)
  18. #define f_out(st) freopen(st,"w",stdout)
  19.  
  20. #define fr(i, a, b) for(int i=a; i<=b; i++)
  21. #define fb(i, a, b) for(int i=a; i>=b; i--)
  22. #define ASST(x, l, r) assert( x <= r && x >= l )
  23.  
  24. #include <ext/pb_ds/assoc_container.hpp>
  25. #include <ext/pb_ds/tree_policy.hpp>
  26.  
  27. #define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0)
  28.  
  29.  
  30. int G[25][25];
  31. int M[25][25];
  32. bool vis[25][25];
  33. int w;
  34. int h;
  35.  
  36.  
  37. int dfs(int x, int y)
  38. {
  39.     cout<<"\n~~~~~~~~x="<<x<<"\ty="<<y<<"\n";
  40.     if(M[x][y]!= 0){
  41.             cout<<"\n#Value already x="<<x<<"\ty="<<y<<"\tM[x][y]="<<M[x][y]<<"\n";
  42.             return M[x][y];
  43.     }
  44.     vis[x][y]= true; 
  45.  
  46.     int a[4];
  47.     memset(a, 0, sizeof(a[0]));
  48.     if(x>0 && G[x-1][y]==1 && !vis[x-1][y]){
  49.     	a[0]= dfs(x-1,y); ///bame
  50.     	//vis[x-1][y]= true; 
  51.  
  52.     } 
  53.     if(x<w-1 && G[x+1][y]==1 && !vis[x+1][y]){
  54.     	a[1]= dfs(x+1, y); ///dane
  55.     	//vis[x+1][y]= true; 
  56.  
  57.     } 
  58.     if(y>0 && G[x][y-1]==1 && !vis[x][y-1]){
  59.     	a[2]= dfs(x, y-1); ///upore
  60.     	//vis[x][y-1]= true; 
  61.     } 
  62.     if(y<h-1 && G[x][y+1]==1 && !vis[x][y+1]){
  63.  
  64.     	//a[3]= dfs(x, y+1); ///niche
  65.  
  66.     }
  67.  
  68.     cout<<"\n#for x="<<x<<"\ty="<<y<<"\ta[0]="<<a[0]<<"\ta[1]="<<a[1]<<"\ta[2]="<<a[2]<<"\ta[3]="<<a[3]<<"\n";
  69.     M[x][y]= 1+a[1]+a[2]+a[3]+a[4];
  70.     cout<<"\nM[x][y]="<<M[x][y]<<"\n";
  71.  
  72.     return M[x][y];
  73.  
  74. }
  75.  
  76.  
  77.  
  78. int main()
  79. {
  80.     IO;
  81.     int t;
  82.     cin>>t;
  83.     for(int tc= 1; tc<=t; tc++){
  84.         ///int w, h;
  85.         cin >> w>> h;
  86.         ///memset(array, 0, sizeof(array[0][0]) * m * n);
  87.         memset(M, 0, sizeof(M[0][0])*w*h);
  88.         memset(vis, false, sizeof(vis[0][0])*w*h); 
  89.         cout<<M[1][0]<<"\n";
  90.         int startx, starty;
  91.         for(int i=0; i<w; i++){
  92.             string s;
  93.             cin>>s;
  94.             for(int j=0; j<h; j++){
  95.                 if(s[j]=='@'){
  96.                     startx= i;
  97.                     starty= j;
  98.                     G[i][j]= 1;
  99.  
  100.                 }
  101.                 else if(s[j]=='#'){
  102.                     G[i][j]= -1;
  103.                 }
  104.                 else{
  105.                     G[i][j]= 1;
  106.                 }
  107.             }
  108.         }
  109.         dfs(startx, starty);
  110.  
  111.     }
  112.  
  113.  
  114.     return 0;
  115. }
  116.  
  117. /*********************************************
  118.  
  119. 1
  120. 4 2
  121. ..
  122. @.
  123. .#
  124. #.
  125.  
  126.  
  127.  
  128.  
  129. ********************************************/
  130.  
Success #stdin #stdout 0s 4272KB
comments (?)
stdin
copy 
1
4 2
..
@.
.#
#.
stdout
copy 
0

~~~~~~~~x=1	y=0

~~~~~~~~x=0	y=0

#for x=0	y=0	a[0]=0	a[1]=-227075381	a[2]=2	a[3]=0

M[x][y]=-227075378

~~~~~~~~x=2	y=0

#for x=2	y=0	a[0]=0	a[1]=-227075381	a[2]=2	a[3]=0

M[x][y]=-227075378

#for x=1	y=0	a[0]=-227075378	a[1]=-227075378	a[2]=933841920	a[3]=0

M[x][y]=706766543
https://ideone.com/UGpeX8
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!