C++(clang++11) 解法, 执行用时: 188ms, 内存消耗: 1656K, 提交时间: 2021-02-14 15:10:59

#include <bits/stdc++.h>
int n, m, d, mp[17][17], val[17], ans = 0, dist[17][17][1 << 10], next[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
bool inque[17][17][1 << 10];
char s[17];
struct { int x, y, val; } bean[17];
struct Node {
    int x, y, status;
    Node (int x = 0, int y = 0, int status = 0) : x(x), y(y), status(status) {}
} cur;
void spfa(int x, int y) {
    memset(dist, 0x7f, sizeof(dist));
    int cur_x, cur_y, cur_status;
    dist[x][y][0] = 0, inque[x][y][0] = true;
    std::queue<Node> que;
    que.emplace(x, y, 0);
    while (!que.empty()) {
        cur = que.front(), que.pop();
        cur_x = cur.x, cur_y = cur.y, cur_status = cur.status;
        inque[cur_x][cur_y][cur_status] = false;
        for (int i = 0; i < 4; i++) {
            int next_x = cur_x + next[i][0], next_y = cur_y + next[i][1];
            if (1 <= next_x && next_x <= n && 1 <= next_y && next_y <= m && mp[next_x][next_y] == 0) {
                int next_status = cur_status;
                for (int k = 1; k <= d; k++) if(next_x<bean[k].x && ((cur_y == bean[k].y && next_y > bean[k].y) || (cur_y > bean[k].y && next_y == bean[k].y))) next_status ^= (1 << (k - 1));
                if (dist[next_x][next_y][next_status] > dist[cur_x][cur_y][cur_status] + 1) {
                    dist[next_x][next_y][next_status] = dist[cur_x][cur_y][cur_status] + 1;
                    if (!inque[next_x][next_y][next_status]) inque[next_x][next_y][next_status], que.emplace(next_x, next_y, next_status);
                }
            }
        }
    }
    for (int status = 0, sum_tmp = 0; status < (1 << d); status++, sum_tmp = 0) {
        for (int i = 1; i <= d; i++) if ((1 << (i - 1)) & status) sum_tmp += bean[i].val;
        ans = std::max(ans, sum_tmp - dist[x][y][status]);
    }
}
int main() {
//    freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= d; i++) scanf("%d", val + i);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; j++) {
            if (s[j] == '#') mp[i][j] = -1;
            else if ((mp[i][j] = s[j] - '0') > 0) bean[mp[i][j]] = {i, j, val[mp[i][j]]};
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (mp[i][j] == 0) spfa(i, j);
    printf("%d\n", ans);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 198ms, 内存消耗: 2020K, 提交时间: 2020-04-25 11:41:45

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int MX=1e5+9;
int dp[20][20][1<<10],mp[20][20],mov[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int n,m,d,ans=0;
char s[20];
struct Node{
    int x,y,val;
}loc[11];

int get(int lasx,int lasy,int nox,int noy,int state){
    for( int i=1 ; i<=d ; i++ ){
        int x=loc[i].x;
        int y=loc[i].y;
        if( ((lasx<x&&x<=nox)||(nox<x&&x<=lasx)) && noy>y )
            state^=(1<<(i-1));
    }
    return state;
}

void spfa(int a,int b){
    memset(dp,inf,sizeof(dp));
    queue<Node> q;
    dp[a][b][0]=0;
    q.push({a,b,0});
    while( !q.empty() ){
        Node temp=q.front();
        q.pop();
        for( int i=0 ; i<4 ; i++ ){
            int x=temp.x+mov[i][0];
            int y=temp.y+mov[i][1];
            if( x<1 || x>n || y<1 || y>m || mp[x][y]==-1 )
                continue;
            int state=get(temp.x,temp.y,x,y,temp.val);
            if( dp[x][y][state]>dp[temp.x][temp.y][temp.val]+1 ){
                dp[x][y][state]=dp[temp.x][temp.y][temp.val]+1;
                q.push({x,y,state});
            }
        }
    }
    for( int i=0 ; i<(1<<d) ; i++ ){
        int an=-dp[a][b][i];
        for( int j=1 ; j<=d ; j++ )
            if( i&(1<<(j-1)) )
                an+=loc[j].val;
        ans=max(ans,an);
    }
}

int main()
{
//    freopen("input.txt","r",stdin);
    scanf("%d %d %d ",&n,&m,&d);
    for( int i=1 ; i<=d ; i++ )
        scanf("%d",&loc[i].val);
    for( int i=1 ; i<=n ; i++ ){
        scanf("%s",s+1);
        for( int j=1 ; j<=m ; j++ ){
            if( s[j]=='#' )
                mp[i][j]=-1;
            else if( s[j]=='0' )
                mp[i][j]=0;
            else{
                mp[i][j]=-1;
                int pos=s[j]-'0';
                loc[pos].x=i;
                loc[pos].y=j;
            }
        }
    }
    for( int i=1 ; i<=n ; i++ )
        for( int j=1 ; j<=m ; j++ )
            if( mp[i][j]==0 )
                spfa(i,j);
    printf("%d\n",ans);
    return 0;
}