1287. Mars Canals(DP)

时间:2021-06-20 20:44:42

1287

水DP

1287. Mars Canals(DP)1287. Mars Canals(DP)
 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
#define N 1402
int dp[N][N][];
char s[N][N];
int main()
{
int i,j,n;
scanf("%d",&n);
for(i = ; i < n ; i++)
cin>>s[i];
dp[][][] = ;
dp[][n-][] = ;
for(i = ; i < n ; i++)
{
dp[][i][] = ;
dp[i][][] = ;
}
for(i = ; i < n ;i++)
for(j = ; j < n ; j++)
{
if(i!=&&j!=&&s[i][j]==s[i-][j-])
{
dp[i][j][] = dp[i-][j-][]+;
}
else
dp[i][j][] = ;
if(i!=&&j!=n-&&s[i][j]==s[i-][j+])
{
dp[i][j][] = dp[i-][j+][]+;
}
else
dp[i][j][] = ;
if(j!=&&s[i][j]==s[i][j-])
{
dp[i][j][] = dp[i][j-][]+;
}
else
dp[i][j][] = ;
if(i!=&&s[i][j]==s[i-][j])
{
dp[i][j][] = dp[i-][j][]+;
}
else
dp[i][j][] = ;
}
int maxz1=,maxz2=;
for(i = ; i < n ; i++)
for(j = ; j < n ; j++)
{
int kk = max(max(dp[i][j][],dp[i][j][]),max(dp[i][j][],dp[i][j][]));
if(s[i][j]=='S')
{
if(kk>maxz1)
{
maxz1 = kk;
}
}
else if(kk>maxz2)
maxz2 = kk;
}
if(maxz1>maxz2)
{
printf("S\n");
printf("%d\n",maxz1);
}
else if(maxz1<maxz2)
{
printf("s\n");
printf("%d\n",maxz2);
}
else
{
printf("?\n");
printf("%d\n",maxz1);
}
return ;
}