C++

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

int price[5][5]={{},{0,100,70,40,0},{0,70,50,30,0},{0,40,30,20,0}};

int N;

int map_[15][15];

int dt[15][15][8210];

int is_safe(int a){

    return a>0&&a<=N;

}

int serch(int x,int y,int bDP){

    if(x==N+1){

        x = 1, y++;

    }

    if(y==N+1)

        return 0;

    if(dt[x][y][bDP]!=-1){

        return dt[x][y][bDP];

    }

    int a=bDP;

    a<<=1;

    a%=1<<(N+1);

    int max_= serch(x+1,y,a);

    if(bDP & (1<<N)){

        return max_;

    }

    if(is_safe(x+1)&&!(bDP & (1<<(N-1)))){

        a=bDP;

        a<<=2;

        a%=1<<(N+1);

        max_=max(max_,serch(x+2,y,a)+price[map_[y][x]][map_[y][x+1]]);

    }

    if(is_safe(y+1)&&!(bDP & 1)){

        a=bDP;

        a|=1;

        a<<=1;

        a%=1<<(N+1);

        max_=max(max_,serch(x+1,y,a)+price[map_[y][x]][map_[y+1][x]]);

    }

    //printf("%d\n",max_);

    return dt[x][y][bDP] = max_;

}

int main()

{

    memset(dt,-1,sizeof(dt));

    scanf("%d",&N);

    for(int i=1;i<=N;i++){

        char str[15];

        scanf("%s",str);

        int j=0;

        while(str[j]!='\0'){

            //map_[i][j+1] = str[j] == 'F' ? 4 : str[j] - 'A' + 1;

            switch(str[j]){

            case 'A':

                map_[i][j+1]=1;

                break;

            case 'B':

                map_[i][j+1]=2;

                break;

            case 'C':

                map_[i][j+1]=3;

                break;

            case 'F':

                map_[i][j+1]=4;

                break;

            }

            j++;

        }

    }

    printf("%d",serch(1,1,0));

    return 0;

}