Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.2 kB
3
Indexable
Never
#include<bits/stdc++.h>
using namespace std;
vector<string> grid;
vector<vector<int>> dp;
int h,w;
int dfs(int i,int j,char ch){
	
	if(i>=h or i<0 or j>=w or j<0)
		return 0;
	
	if(ch == ('Z' + 1))
		return 0;
		
	if(grid[i][j] != ch )
		return 0;
		
	if(dp[i][j] != -1)
		return dp[i][j];
	
	
	int ans = 0;
	ch++;
	ans = max(dfs(i+1,j,ch),dfs(i,j+1,ch));
	ans = max(ans,dfs(i-1,j,ch));
	ans = max(ans,dfs(i,j-1,ch));
	ans = max(ans,dfs(i+1,j+1,ch));
	ans = max(ans,dfs(i-1,j-1,ch));
	ans = max(ans,dfs(i-1,j+1,ch));
	ans = max(ans,dfs(i+1,j-1,ch));
	
	ans += 1;
	dp[i][j] = ans;
	
	return ans;
	
}

bool solve(int n){
	cin>>h>>w;
	
	if(h==0 and w==0)
		return false;
	
	grid.resize(h);
	dp.resize(h);
	
	for(int i=0;i<h;i++){
		cin>>grid[i];
		dp[i].resize(w);
	}
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++)
			dp[i][j] = -1;
	}
	
	
	int ans = 0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(grid[i][j] == 'A')
				ans = max(ans,dfs(i,j,'A'));
		}
	}
	
	
	cout<<"Case "<<n<<": "<<ans<<endl;
	
	return true;
}

int main() {
	// your code goes here
	
	int t;
	int num = 1;
	
	while(true){
		
		if(!solve(num))
			break;
		num++;
	}
	return 0;
}