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.     	cout<<"\nGoing LEFT x="<<x<<"\ty="<<y<<"\n"; 
  50.     	a[0]= dfs(x-1,y); ///bame
  51.     	//vis[x-1][y]= true; 
  52.  
  53.  
  54.     } 
  55.     if(x<w-1 && G[x+1][y]==1 && !vis[x+1][y]){
  56.     	cout<<"\nGoing RIGHT x="<<x<<"\ty="<<y<<"\n"; 
  57.     	a[1]= dfs(x+1, y); ///dane
  58.     	//vis[x+1][y]= true; 
  59.  
  60.     } 
  61.     if(y>0 && G[x][y-1]==1 && !vis[x][y-1]){
  62.     	cout<<"\nGoing UP x="<<x<<"\ty="<<y<<"\n"; 
  63.     	a[2]= dfs(x, y-1); ///upore
  64.     	//vis[x][y-1]= true; 
  65.     } 
  66.     if(y<h-1 && G[x][y+1]==1 && !vis[x][y+1]){
  67.     	cout<<"\nGoing DOWN x="<<x<<"\ty="<<y<<"\n"; 
  68.  
  69.     	a[3]= dfs(x, y+1); ///niche
  70.  
  71.     }
  72.  
  73.     cout<<"\n#for x="<<x<<"\ty="<<y<<"\ta[0]="<<a[0]<<"\ta[1]="<<a[1]<<"\ta[2]="<<a[2]<<"\ta[3]="<<a[3]<<"\n";
  74.     M[x][y]= 1+a[1]+a[2]+a[3]+a[4];
  75.     cout<<"\nM[x][y]="<<M[x][y]<<"\n";
  76.  
  77.     return M[x][y];
  78.  
  79. }
  80.  
  81.  
  82.  
  83. int main()
  84. {
  85.     IO;
  86.     int t;
  87.     cin>>t;
  88.     for(int tc= 1; tc<=t; tc++){
  89.         ///int w, h;
  90.         cin >> w>> h;
  91.         ///memset(array, 0, sizeof(array[0][0]) * m * n);
  92.         memset(M, 0, sizeof(M[0][0])*w*h);
  93.         memset(vis, false, sizeof(vis[0][0])*w*h); 
  94.         cout<<M[1][0]<<"\n";
  95.         int startx, starty;
  96.         for(int i=0; i<w; i++){
  97.             string s;
  98.             cin>>s;
  99.             for(int j=0; j<h; j++){
  100.                 if(s[j]=='@'){
  101.                     startx= i;
  102.                     starty= j;
  103.                     G[i][j]= 1;
  104.  
  105.                 }
  106.                 else if(s[j]=='#'){
  107.                     G[i][j]= -1;
  108.                 }
  109.                 else{
  110.                     G[i][j]= 1;
  111.                 }
  112.             }
  113.         }
  114.         dfs(startx, starty);
  115.  
  116.     }
  117.  
  118.  
  119.     return 0;
  120. }
  121.  
  122. /*********************************************
  123.  
  124. 1
  125. 4 2
  126. ..
  127. @.
  128. .#
  129. #.
  130.  
  131.  
  132.  
  133.  
  134. ********************************************/
  135.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
1
2 4
..
@.
.#
#.
stdout
copy 
0

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

Going LEFT x=1	y=0

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

Going DOWN x=0	y=0

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

Going RIGHT x=0	y=1

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

Going DOWN x=1	y=1

~~~~~~~~x=1	y=2

Going LEFT x=1	y=2

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

Going DOWN x=0	y=2

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

Going RIGHT x=0	y=3

~~~~~~~~x=1	y=3

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

M[x][y]=-1394053085

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

M[x][y]=1506861125

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

M[x][y]=112808039

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

M[x][y]=-1394053085

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

M[x][y]=1506861125

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

M[x][y]=112808039

#for x=0	y=0	a[0]=0	a[1]=-88075744	a[2]=-1394053088	a[3]=112808039

M[x][y]=-1369320792

#for x=1	y=0	a[0]=-1369320792	a[1]=-284214272	a[2]=-1394053088	a[3]=1

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