fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. char arr[209][209];
  5. int n,m;
  6. int val[209][209][2];
  7.  
  8. int dp(int i,int j,int p){
  9. 	//cout<<i<<" "<<j<<" "<<p<<endl;
  10. 	if(i>=n && j>=m){return 0;}
  11. 	if(val[i][j][p] != -1){return val[i][j][p];}
  12.  
  13. 	int sum=0;
  14. 	if(p==0){
  15. 		if(j>0){
  16. 			if(arr[i][j-1]!='#'){
  17. 				if(arr[i][j-1]=='T'){sum = max(sum,dp(i,j-1,0)+1);}
  18. 				else{sum = max(sum,dp(i,j-1,0));}
  19. 			}
  20. 		}
  21. 		if(i<n-1){
  22. 			if(arr[i+1][j]!='#'){
  23. 				if(arr[i+1][j]=='T'){sum = max(sum,dp(i+1,j,1)+1);}
  24. 				else{sum = max(sum,dp(i+1,j,1));}
  25. 			}
  26. 		}
  27. 	}
  28. 	if(p==1){
  29. 		if(j<m-1){
  30. 			if(arr[i][j+1]!='#'){
  31. 				if(arr[i][j+1]=='T'){sum = max(sum,dp(i,j+1,1)+1);}
  32. 				else{sum = max(sum,dp(i,j+1,1));}
  33. 			}
  34. 		}
  35. 		if(i<n-1){
  36. 			if(arr[i+1][j]!='#'){
  37. 				if(arr[i+1][j]=='T'){sum = max(sum,dp(i+1,j,0)+1);}
  38. 				else{sum = max(sum,dp(i+1,j,0));}
  39. 			}
  40. 		}
  41. 	}
  42. 	val[i][j][p] = sum;
  43. 	return val[i][j][p];
  44. }
  45.  
  46. int main(){
  47. 	#ifndef ONLINE_JUDGE
  48. 	freopen("input.in","r",stdin);
  49. 	freopen("output.out","w",stdout);
  50. 	#endif
  51.  
  52. 	int t;
  53. 	cin>>t;
  54.  
  55. 	while(t--){
  56. 		cin>>n>>m;
  57. 		for(int i=0;i<n;i++){
  58. 			for(int j=0;j<m;j++){
  59. 				cin>>arr[i][j];
  60. 			}
  61. 		}
  62. 		int ans=0;
  63. 		memset(val,-1,sizeof(val));
  64. 		if(arr[0][0]!='#'){
  65. 			ans = dp(0,0,1);
  66. 			if(arr[0][0]=='T'){ans++;}
  67. 		}
  68. 		cout<<ans<<endl;
  69. 	}
  70. }
Success #stdin #stdout 0s 16448KB
comments (?)
stdin
copy 
4

5 5

0TTTT

T#T#0

#TT#T

T00T0

T0#T0

1 1

T

3 3

T#T

TTT

T#T

1 1

#
stdout
copy 
8
1
3
0
https://ideone.com/PVJDVM
language:
C++ (gcc 8.3)
created:
7 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!