fork download
copy 
  1. //I tried dfs on grid and memoized the solution but this is getting
  2. //wrong somewhere. Can you help please.
  3.  
  4. // problem : spoj/ABCPATH/
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define nl "\n"
  9.  
  10. int n,m,x,y,rr;
  11. char a[55][55];
  12. int dp[55][55];
  13.  
  14.  
  15. int dx[] = {-1,-1,0,1,1,1,0,-1};
  16. int dy[] = {0,1,1,1,0,-1,-1,-1};
  17.  
  18. bool isValid(int fx, int fy, char cp)
  19. {
  20. 	cp++;
  21. 	if(fx<0||fx>=n||fy<0||fy>=m) return false;
  22. 	if(a[fx][fy]!=cp) return false;
  23.  
  24. 	return true;
  25. }
  26.  
  27. int dfs(int sx, int sy)
  28. {
  29. 	if(dp[sx][sy]!=-1) return dp[sx][sy];
  30.  
  31. 	int pp=1;
  32.  
  33. 	int df = 0;
  34.  
  35. 	for(int i=0; i<8; i++)
  36. 	{
  37. 		int nx = sx+dx[i];
  38. 		int ny = sy+dy[i];
  39.  
  40. 		if(isValid(nx,ny,a[sx][sy]))
  41. 		{
  42. 			int rp = dfs(nx,ny);
  43. 			df = max(df,rp);
  44. 		}
  45. 	}
  46. 	pp+=df;
  47. 	return dp[sx][sy] = pp;
  48.  
  49. }
  50.  
  51. int main () {
  52. 	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);	
  53. //    freopen("input.txt", "r", stdin);
  54. 		int pp=1;
  55. 		while(1)
  56. 		{
  57.  
  58. 			cin>>n>>m;
  59. 			if(n==0 && m==0) break;
  60.  
  61. 			memset(dp,-1,sizeof(dp));
  62. 			vector<pair<int,int> > p;
  63. 			p.clear();
  64.  
  65. 			int ans=0;
  66. 			for(int i=0; i<n; i++)
  67. 			{
  68. 				for(int j=0; j<m; j++)
  69. 				{
  70. 					cin>>a[i][j];
  71. 					if(a[i][j]=='A') p.push_back({i,j});
  72. 				}
  73. 			}
  74. 			if(p.size()==0)
  75. 			{
  76. 				cout<<ans<<nl;
  77. 				continue;
  78. 			}
  79. 			for(int i=0; i<p.size(); i++)
  80. 			{
  81.  
  82. 				rr = dfs(p[i].first,p[i].second);
  83. 				ans = max(ans,rr);
  84. 			}
  85. 			cout<<"Case "<<pp++<<": "<<ans<<nl;
  86. 		}
  87.  
  88. return 0;
  89. }
  90.  
  91.  
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
4 3
ABE
CFG
BDH
ABC
0 0
stdout
copy 
Case 1: 4
https://ideone.com/vULGyp
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!