2 / 2
Dec 2021

#include <bits/stdc++.h>
using namespace std;

int dfs(int i,int j,char c,vector<vector>&matrix, vector<vector >&dp){
int h=matrix.size();
int w=matrix[0].size();
if(i<0||j<0||i>h-1||j>w-1)
return 0;

if(matrix[i][j]==c+1){
   	if(dp[i][j]!=0)
return dp[i][j];
	int a=dfs(i-1,j,matrix[i][j],matrix,dp)+1;
	int b=dfs(i,j-1,matrix[i][j],matrix,dp)+1;
	int c=dfs(i+1,j,matrix[i][j],matrix,dp)+1;
	int d=dfs(i,j+1,matrix[i][j],matrix,dp)+1;
	int e=dfs(i-1,j-1,matrix[i][j],matrix,dp)+1;
	int f=dfs(i-1,j+1,matrix[i][j],matrix,dp)+1;
	int g=dfs(i+1,j-1,matrix[i][j],matrix,dp)+1;
	int h=dfs(i+1,j+1,matrix[i][j],matrix,dp)+1;
	 dp[i][j]= std::max({a,b,c,d,e,f,g,h});
	 return dp[i][j];
}
return 0;

}
int main() {
// your code goes here
int h,w;
cin>>h>>w;
int count=1;
while(h!=0&&w!=0){
vector<vector >dp(h,vector (w,0));
int ans=INT_MIN;
vector<vector >matrix(h,vector (w,’#’));
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
cin>>matrix[i][j];
// cout<<“hello”;
}
}

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(matrix[i][j]=='A')
		ans=max(ans,dfs(i,j,'@',matrix,dp));
		}}
		cout<<"Case "<<count<<": "<<ans<<endl;
		count++;
		h=0,w=0
		cin>>h>>w;
}
return 0;

}

  • created

    Dec '21
  • last reply

    Dec '21
  • 1

    reply

  • 661

    views

  • 2

    users

  • 1

    link