Codeforces Round #316 (Div. 2) E

E Pig and Palindromes
n*m의 격자입니다. 격자마다 문자가 있습니다. 왼쪽 상단에서 오른쪽 하단까지 (아래로 또는 오른쪽으로만) 가야 합니다. 지나가는 문자를 연결해서 회문열로 만들어야 합니다. 몇 가지 방안이 있는지 물어보십시오.
        dp.pp(i, j, k)는 기점에서 i행 j열까지의 칸을 표시하고 대칭적인 칸이 k행(열로 계산할 수 있음)의 방안수를 나타낸다. 마지막 답은 사선 대칭축의 방안수의 합이다.그러나 이렇게 하면 메모리를 초과할 수 있기 때문에 스크롤 수조압이 1차적으로 i% 2로 바뀌어야 한다.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

#define ll long long

const int mod = 1000000007;

char mp[510][510];
int dp[2][510][510];

int n,m;
inline bool verrify(int a,int b,int c,int d){
    if(a<1||a>n||b<1||b>m||c<a||c>n||d<b||d>m)return 0;
    return 1;
}

int main(){
    cin>>n>>m;
    int mid = (n+m+2)>>1;
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
    }

    if(mp[1][1]==mp[n][m]){
        dp[1][1][n]=1;
    }

    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m&&(i+j)<=mid;j++){
            if(i==1&&j==1)continue;
            for(int ii=i;ii<=n;ii++){
                int jj=2+n+m-i-j-ii;
                if(jj<j||jj>m)continue;
                dp[i%2][j][ii]=0;
                if(mp[i][j]==mp[ii][jj]){
                    if(verrify(i-1,j,ii+1,jj))dp[i%2][j][ii]+=dp[(i-1)%2][j][ii+1];
                    dp[i%2][j][ii]%=mod;
                    if(verrify(i-1,j,ii,jj+1))dp[i%2][j][ii]+=dp[(i-1)%2][j][ii];
                    dp[i%2][j][ii]%=mod;
                    if(verrify(i,j-1,ii+1,jj))dp[i%2][j][ii]+=dp[i%2][j-1][ii+1];
                    dp[i%2][j][ii]%=mod;
                    if(verrify(i,j-1,ii,jj+1))dp[i%2][j][ii]+=dp[i%2][j-1][ii];
                    dp[i%2][j][ii]%=mod;
                }
                if(i+j==mid){
                    ans+=dp[i%2][j][ii];
                    ans%=mod;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}