思路与算法

把每个格子作为一个顶点。相邻格子之间可移动；任意两个边缘格之间也可直接转移，因为到达边缘后可离开并换一个入口。已经访问的格子不能再使用。

状态dp[S][v]表示已经取走的集合为S、当前停在v时的最大得分。只从边缘格初始化单格状态，得分为该格值。若w未访问且与v有合法转移，则新得分为dp[S][v]+(已有格数+1)*a[w]，更新dp[S加入w][w]。掩码最多16位，格数用popcount取得。

取数值非负，任何尚未结束的合法路径都能继续到某个真实终态且不减少得分。因此可对所有可达状态取最大值，而不必单独限制只在无法操作时更新答案。

正确性说明

原规则允许四方向走到未取格，也允许在边缘离开后从任意未取边缘重新进入。所建边集合恰好描述这两类操作；反向同样合法，且都要求新格未在S中，不会穿过已取格。

一个可达状态的未来只依赖已取集合和最后位置，下一次取数序号由集合大小唯一确定。对相同(S,v)，较大累计得分不影响后续合法性，且在任何同一后续操作下都不小于较小得分，因此只保留最大值正确。初始状态遍历所有合法边缘起点。每条合法路径的最后一步都在转移中出现，反过来每个转移也给出合法路径，按集合大小归纳DP准确。

若某个可达状态尚有操作，取下一个非负格子增加非负分数；有限格数保证反复延伸最终停在合法终态。因此所有状态的最大值不超过某个真实终态分数，而终态也是状态之一，两者最大值相同，最终答案正确。

复杂度

令K=MN<=16。建立移动掩码O(K)，初始化2^KK个得分槽O(K2^K)。每个状态至多尝试K个新格，总时间O(K²2^K)，空间O(K2^K)。得分最大为99999(1+...+16)=13599864，使用int并以-1区分不可达与零分。表主体约4MiB，保留原64MiB资源。

易错点

1. 起点必须在边缘，不能把任意格都作为第一格。
2. 边缘可以直接换到另一未取边缘，无需在格内寻找连接路径。
3. 得分序号从1开始，下一序号是已取数量加1；零值仍会占一次序号。
4. 不能再次经过已取格，掩码要参与所有移动判定。
5. 最大化所有前缀状态依赖非负取值；若允许负数，这个终态论证就不成立。
6. 覆盖1格、线形全边缘、4乘4、中心高值、全零和第二组公开示例。

参考代码（C++11）

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    int N = m * n;
    vector<int> a(N), moves(N);
    for (int &v : a)
        cin >> v;
    unsigned border = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (i == 0 || j == 0 || i + 1 == m || j + 1 == n)
                border |= 1u << (i * n + j);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            int v = i * n + j;
            if (i)
                moves[v] |= 1u << (v - n);
            if (i + 1 < m)
                moves[v] |= 1u << (v + n);
            if (j)
                moves[v] |= 1u << (v - 1);
            if (j + 1 < n)
                moves[v] |= 1u << (v + 1);
            if (border >> v & 1)
                moves[v] |= border;
            moves[v] &= ~(1u << v);
        }
    unsigned limit = 1u << N;
    vector<int> dp((size_t)limit * N, -1);
    for (int v = 0; v < N; ++v)
        if (border >> v & 1)
            dp[(size_t)(1u << v) * N + v] = a[v];
    int ans = 0;
    for (unsigned s = 1; s < limit; ++s) {
        int rank = __builtin_popcount(s) + 1;
        for (int v = 0; v < N; ++v) {
            int cur = dp[(size_t)s * N + v];
            if (cur < 0)
                continue;
            ans = max(ans, cur);
            unsigned rest = moves[v] & ~s;
            while (rest) {
                unsigned bit = rest & -rest;
                int w = __builtin_ctz(bit);
                int &next = dp[(size_t)(s | bit) * N + w];
                next = max(next, cur + rank * a[w]);
                rest -= bit;
            }
        }
    }
    cout << ans << '\n';
}