[NICE_September] pF-架設電纜線(Cable)

#include<stdio.h>
#include<vector>
using namespace std;
vector<int> vec;
char s[1005][1005];
int dp[1005][1005][2]={0},add[1005][1005][2]={0},p[1005][1005][2];
int main(){
    int n,m,i,j,k,x,y,z,v;
    scanf("%d%d",&n,&m);
    n++,m++;
    for(i=1;i<=n;i++)
        scanf("%s",&s[i][1]);
    p[1][1][0]=p[1][1][1]=-1;
    for(i=2;i<=m;i++){
        p[1][i][1]=1;
        dp[1][i][0]=-99999999;
        dp[1][i][1]=dp[1][i-1][1];
        if(s[1][i]=='X') dp[1][i][1]++;
    }
    for(i=2;i<=n;i++){
        p[i][1][1]=0;
        dp[i][1][1]=-99999999;
        dp[i][1][0]=dp[i-1][1][0];
        if(s[i][1]=='X') dp[i][1][0]++;
    }
    for(i=2;i<=n;i++){
        for(j=2;j<=m;j++){
            if(dp[i-1][j][0]<=dp[i-1][j][1]){
                dp[i][j][0]=dp[i-1][j][1],p[i][j][0]=1,add[i][j][0]=add[i-1][j][1]+1;
            }
            if(dp[i-1][j][0]>dp[i-1][j][1] || (dp[i-1][j][0]==dp[i-1][j][1] && add[i-1][j][0]<=add[i][j][0])){
                dp[i][j][0]=dp[i-1][j][0],add[i][j][0]=add[i-1][j][0],p[i][j][0]=0;
            }
            if(dp[i][j-1][0]<=dp[i][j-1][1]){
                dp[i][j][1]=dp[i][j-1][1],p[i][j][1]=1,add[i][j][1]=add[i][j-1][1];
            }
            if(dp[i][j-1][0]>dp[i][j-1][1] || (dp[i][j-1][0]==dp[i][j-1][1] && add[i][j-1][0]+1<=add[i][j][1])){
                dp[i][j][1]=dp[i][j-1][0],add[i][j][1]=add[i][j-1][0]+1,p[i][j][1]=0;
            }
            if((i!=n || j!=m) && s[i][j]=='X') dp[i][j][0]++,dp[i][j][1]++;
        }
    }
    if(dp[n][m][1]!=dp[n][m][0]){
        if(dp[n][m][1]>dp[n][m][0]) v=1;
        else v=0;
    }
    else{
        if(add[n][m][1]<=add[n][m][0]) v=1;
        else v=0;
    }
    printf("%d\n",dp[n][m][v]);
    x=n,y=m;
    while(p[x][y][v]!=-1){
        vec.push_back(v);
        z=p[x][y][v];
        if(v==1) y--;
        else x--;
        v=z;
    }
    for(i=vec.size()-1;i>=0;i--){
        if(vec[i]==0) putchar('D');
        else putchar('R');
    }
    puts("");
}