NC24220. [USACO 2015 Ope G]Palindromic Paths
描述
ABCD BXZX CDXB WCBA
Each day, Bessie the cow walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. Bessie keeps track of the string that she generates during this process, built from the letters she walks across. She gets very disoriented, however, if this string is a palindrome (reading the same forward as backward), since she gets confused about which direction she had walked.
Please help Bessie determine the number of distinct routes she can take that correspond to palindromes. Different ways of obtaining the same palindrome count multiple times. Please print your answer modulo 1,000,000,007.
输入描述
The first line of input contains NN, and the remaining NN lines contain the NN rows of the grid of fields. Each row contains NNcharacters that are in the range A..Z.
输出描述
Please output the number of distinct palindromic routes Bessie can take, modulo 1,000,000,007.
示例1
输入:
4 ABCD BXZX CDXB WCBA
输出:
12
说明:
Bessie can make the following palindromesC++14(g++5.4) 解法, 执行用时: 115ms, 内存消耗: 2552K, 提交时间: 2020-08-31 22:11:45
#include<iostream>
#define ll long long
#define rint register int
using namespace std;
char a[501][501];
int n;
ll f[501][501],ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
if(a[1][1]!=a[n][n])
{
cout<<0;
return 0;
}
f[1][1]=1;
for(rint i=3;i<=n+1;i++)
for(rint j=i-1;j>=1;j--)
for(rint k=i-1;k>=1;k--)
{
if(a[j][i-j]==a[n-i+k+1][n-k+1])
f[j][k]=(f[j][k]+f[j-1][k-1]+f[j-1][k]+f[j][k-1])%1000000007;
else f[j][k]=0;
}
for(int i=1;i<=n;i++)
ans=(ans+f[i][i])%1000000007;
cout<<ans;
}
C++11(clang++ 3.9) 解法, 执行用时: 302ms, 内存消耗: 2788K, 提交时间: 2020-03-14 20:45:34
#include<iostream>
#define rint register int
using namespace std;
char a[501][501];
int n;
long long f[501][501],ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
if(a[1][1]!=a[n][n])
{
cout<<0;
return 0;
}
f[1][1]=1;
for(rint i=3;i<=n+1;i++)
for(rint j=i-1;j>=1;j--)
for(rint k=i-1;k>=1;k--)
{
if(a[j][i-j]==a[n-i+k+1][n-k+1])
f[j][k]=(f[j][k]+f[j-1][k-1]+f[j-1][k]+f[j][k-1])%1000000007;
else f[j][k]=0;
}
for(int i=1;i<=n;i++)
ans=(ans+f[i][i])%1000000007;
cout<<ans;
}