fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define what_is(x) cerr << #x << " is " << x << endl;
  4. #define IOS ios::sync_with_stdio(false); cin.tie(0);
  5. typedef long long ll;
  6. const int N = 50+5;
  7. const int INF = 1e9;
  8. const int MOD = 1e9+7;
  9.  
  10. int n, m;
  11. char c[N][N];
  12. int dp[N][N];
  13. int vis[N][N];
  14. int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
  15. int dy[] = {0, 1, 1, 1,0 , -1, -1, -1};
  16. //dp[i][j]: the longest consecutive sequence start at (i,j)
  17. int dfs(int x, int y){
  18. 	dp[x][y] = 1;
  19. 	int mx = 0;
  20. 	for(auto i:dx){
  21. 		for(auto j:dy){
  22. 			int nx = x+i, ny = y+j; //new_x, new_y
  23. 			if (nx<0 || ny<0 || nx>=n || ny>=m) continue;
  24. 			if (c[nx][ny]-c[x][y] != 1) continue;
  25. 			if (dp[nx][ny] != 0) {
  26. 				mx = max(mx, dp[nx][ny]);
  27. 				continue;
  28. 			}
  29. 			mx = max(mx, dfs(nx, ny));
  30. 		}
  31. 	}	
  32. 	dp[x][y] += mx;
  33. 	return dp[x][y];
  34. }
  35. int main()
  36. {
  37. 	IOS
  38. 	// freopen("input.txt", "r", stdin);
  39. 	int tc = 1;
  40. 	while(1){
  41. 		cin >> n >> m;
  42. 		if (n == 0 && m == 0) break;
  43. 		for(int i=0; i<n; i++){
  44. 			for (int j=0; j<m; j++){
  45. 				cin >> c[i][j];
  46. 			}
  47. 		}
  48. 		memset(dp, 0, sizeof dp);
  49. 		for(int i=0; i<n; i++){
  50. 			for(int j=0; j<m; j++){
  51. 				if (dp[i][j] == 0) dfs(i, j);
  52. 			}
  53. 		}
  54. 		int ans = 0;
  55. 		for(int i=0; i<n; i++){
  56. 			for(int j=0; j<m; j++){
  57. 				if (c[i][j] == 'A') ans = max(ans, dp[i][j]);
  58. 			}
  59. 		}
  60. 		cerr << "Case " << tc++ << ": " << ans << endl; 
  61. 	}
  62.  
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pG1R77
language:
C++14 (gcc 8.3)
created:
5 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!