#1957817

Solution for 2538: Stack Maze by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 63    
00.12 sec    32016 KB    89 lines     2356 bytes    2016-08-10 15:46
#include<bits/stdc++.h>

using namespace std;

struct I{I(){ios::sync_with_stdio(false);cin.tie(0);}}init;

typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<VVV> VVVV;
typedef tuple<int,int> P;
typedef vector<P> VP;
typedef vector<VP> VVP;
int isLC(char c){
    if('a'<=c&&c<='z')return c-'a';
    else return -1;
}
int isUC(char c){
    if('A'<=c&&c<='Z')return c-'A';
    else return -2;
}
bool inner(int lb,int c,int ub){
    return lb<=c&&c<=ub;
}
int f(int rbg,int red,int cbg,int ced,vector<string>& s,VVVV &memo,VVP&U){
    if(memo[rbg][cbg][red][ced]!=-2)return memo[rbg][cbg][red][ced];
    //cout<<cbg<<" "<<ced<<endl;
    int R=1+red-rbg;
    int C=1+ced-cbg;
    VV dp(R,V(C,-1));
    dp[0][0]=0;
    int x=isLC(s[rbg][cbg]);
    int y=isUC(s[red][ced]);
    if(x==y){
        s[rbg][cbg]='.';
        s[red][ced]='.';
        dp[0][0]++;
    }
    for(int r=rbg;r<=red;r++){
        for(int c=cbg;c<=ced;c++){
            int i=r-rbg;
            int j=c-cbg;
            if(dp[i][j]==-1)continue;
            int id=isLC(s[r][c]);
            if(id>=0){
                for(auto &it:U[id]){
                    int nr,nc;
                    tie(nr,nc)=it;
                    if(inner(r,nr,red)&&inner(c,nc,ced)&&isLC(s[r][c])==isUC(s[nr][nc])){
                        int val=f(r,nr,c,nc,s,memo,U);
                        int ni=nr-rbg;
                        int nj=nc-cbg;
                        if(val!=-1)
                            dp[ni][nj]=max(dp[ni][nj],dp[i][j]+val);
                    }
                }            
            }
            if(r!=red&&s[r+1][c]!='#')dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            if(c!=ced&&s[r][c+1]!='#')dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
        }     
    }
    if(x==y){
        s[rbg][cbg]=x+'a';
        s[red][ced]=y+'A';
    }
    //cout<<rbg<<" "<<red<<" "<<dp[R-1][C-1]<<endl;
    return memo[rbg][cbg][red][ced]=dp[R-1][C-1];
}


int main(){
    for(int R,C;cin>>R>>C,R+C;){
        vector<string> s(R);
        for(auto &it:s)cin>>it;
        VVP uc(26);
        for(int i=0;i<R;i++)
            for(int j=0;j<C;j++){
                int id=isUC(s[i][j]);
                if(id>=0)uc[id].push_back(P(i,j));
            }
        VVVV memo(R,VVV(C,VV(R,V(C,-2))));
        cout<<f(0,R-1,0,C-1,s,memo,uc)<<endl;

    }

    return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 C++14 CPU: 00.12 sec Memory: 32016 KB Length: 2356 B 2016-08-10 15:46 2016-08-10 15:46
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.12 sec 32016 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags