题解：P7472 【[NOI Online 2021 入门组] 吃豆人（民间数据）】

这道题大家可以先画画图，然后发现周围除四个角的任意一点出发，总能回到该点。因此我们可以只求出第一行开始遍历的求和答案，注意四角的两点需要特判！
至于如何求一个环之和，我们就找规律。令一开始往右下的方向走，则不断碰壁更改的方向依次是：右下 -> 左下 -> 左上->右上。直到回到原位。这样我们把第一行全部遍历后就能分别得到每条路径对应的豆子数量之和。所以下一步我们需要找到两条不同的路径减去重复部分后的最大值。
以题目中的图为例，我们再次找规律，设选择的两条路径第一行的横坐标为 $x,y(x < y)$，发现只有第一行两点间的距离为偶数时才可能出现交点。其次，易得两点距离为$y - x$ 则交点分别在任意一条路径与最大方框交点的向上、下、左、右的 $\frac{y-x}{2}$ 的点上（感性理解一下，就是如下图二箭头所指的四个点)。

注意的是，重复需要减去的点也有可能会有重叠。因此，需要判断重复的点是否相同。这个判断用 if 就行，千万不要用什么 map 等去判断！！！

最后发一下完整代码，没理解的看一下具体的实现：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e3 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,cnt,ans;
int a[MAX][MAX],num[MAX];
bool vis[MAX];
void search (int x,int y,int st);
int work (int x,int y);
int main ()
{
    freopen ("pacman.in","r",stdin);
    freopen ("pacman.out","w",stdout);
    n = read ();
    for (int i = 1;i <= n;++i) 
        for (int j = 1;j <= n;++j) a[i][j] = read ();
    for (int i = 1;i <= n;++i)
    {
        cnt = 0;
        if (i == 1) for (int j = 1;j <= n;++j) cnt += a[j][j];
        else if (i == n) for (int j = 1;j <= n;++j) cnt += a[n - j + 1][j];
        else search (1,i,1);
        num[i] = cnt;
    }
    for (int i = 1;i <= n;++i)//找到最优解
        for (int j = i + 1;j <= n;++j) ans = max (ans,work (i,j));
    printf ("%d\n",ans);
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void search (int x,int y,int st)
{
    if (x == 1)
    {
        if (vis[y]) return ;//回到原位
        else vis[y] = 1;
    }
    cnt += a[x][y];//累加
   //不同方向
    if (y == 1) st = 3;
    if (y == n) st = 2;
    if (x == n) st = 4;
    if (st == 1) search (x + 1,y + 1,st);
    if (st == 2) search (x + 1,y - 1,st);
    if (st == 3) search (x - 1,y + 1,st);
    if (st == 4) search (x - 1,y - 1,st);
}
int work (int x,int y)
{
    int sum = num[x] + num[y],same = 0;
    if ((y - x) % 2 == 1) return sum;//没有交点的情况
    int len = (y - x) / 2;
    same += a[len + 1][x + len];//判重复的方向，注意不要重复减去！！！不要用map
    if (x + len != len + 1) same += a[x + len][len + 1];
    if ((n - x) + 1 - len != x + len && n - len != 1 + len && (n - x) + 1 - len != 1 + len && n - len != x + len) same += a[(n - x) + 1 - len][n - len];
    if ((n - x) + 1 - len != x + len && n - len != 1 + len && (n - x) + 1 - len != 1 + len && n - len != x + len && (n - x + 1) - len != n - len) same += a[n - len][(n - x) + 1 - len];
    return sum - same;    
}