Description:

在 $N\times M$ 的网格中求一条回路使权值之和最大。

$2\le N\le 100$ $2\le M \le 6$

Solution:

插头 $DP$ ，用括号序列表示连通性，每次转移时，可以新增一对插头，延续插头，合并双左插头，合并双右插头，合并右左插头，在没有别的插头时可以合并左右插头，此时更新答案，不向下转移。注意合并同类插头时找下一个不配对的插头换插头。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 105

#define MAXM 8

#define INF 0x3f3f3f3f

typedef long long ll;

int n,m;

int map[MAXN][MAXM];

ll ans = -INF;

#define HASH 30007

#define STATE 3000000

struct hash

{

	int lin[HASH],nxt[STATE],siz;

	ll dat[STATE],f[STATE];

	void init(){memset(lin,0,sizeof(lin));siz = 0;}

	void add(ll sta,ll ans)

	{

		int has = sta % HASH;

		for(int i = lin[has];i != 0;i = nxt[i])if(dat[i] == sta){f[i] = max(f[i],ans);return;}

		++siz;dat[siz] = sta;f[siz] = ans;nxt[siz] = lin[has];lin[has] = siz;

		return;

	}

}h[2];

int code[MAXM],code_[MAXM];

void shift(int *code,int *code_,bool tag)

{

	if(tag)

	{

		for(int i = m;i > 0;--i)code_[i] = code[i - 1];

		code_[0] = 0;

	}

	else

	{

		for(int i = m;i >= 0;--i)code_[i] = code[i];

	}

	return;

}

ll encode(int *code,int m)

{

	ll res = 0;

	for(int i = 0;i <= m;++i)

	{

		res = res << 2;

		res |= code[i];

	}

	return res;

}

void decode(int *code,int m,ll sta)

{

	for(int i = m;i >= 0;--i)

	{

		code[i] = sta & 3;

		sta = sta >> 2;

	}

	return;

}

void dp(int i,int j,int cur)

{

	int left,up;

	bool flag;

	if(j == m)flag = true;

	for(int k = 1;k <= h[cur].siz;++k)

	{

		decode(code,m,h[cur].dat[k]);

		left = code[j - 1];up = code[j];

		if(left == 0 && up == 0)

		{

			if(i < n && j < m)

			{

				code[j - 1] = 1;code[j] = 2;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + map[i][j]);

			}

			code[j - 1] = 0;code[j] = 0;

			shift(code,code_,flag);

			h[cur ^ 1].add(encode(code_,m),h[cur].f[k]);

		}

		if((left == 0 && (up == 1 || up == 2)) || ((left == 1 || left == 2) && up == 0))

		{

			int t;

			if(left == 1 || left == 2)t = left;

			else t = up;

			if(i < n)

			{

				code[j - 1] = t;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + map[i][j]);

			}

			if(j < m)

			{

				code[j - 1] = 0;code[j] = t;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + map[i][j]);

			}

		}

		if(left != 0 && up != 0)

		{

			if(left == 1 && up == 1)

			{

				int cnt = 0;

				int t;

				for(t = j + 1;t <= m;++t)

				{

					if(code[t] == 1)++cnt;

					if(code[t] == 2)

					{

						if(cnt == 0){code[t] = 1;break;}

						else --cnt;

					}

				}

				code[j - 1] = code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + map[i][j]);

				code[t] = 2;

			}

			if(left == 2 && up == 2)

			{

				int cnt = 0;

				int t;

				for(t = j - 2;t >= 0;--t)

				{

					if(code[t] == 2)++cnt;

					if(code[t] == 1)

					{

						if(cnt == 0){code[t] = 2;break;}

						else --cnt;

					}

				}

				code[j - 1] = code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + map[i][j]);

				code[t] = 1;

			}

			if(left == 1 && up == 2)

			{

				bool tag = true;

				for(int t = 0;t <= j - 2;++t)if(code[t] != 0){tag = false;break;}

				for(int t = j + 1;t <= m;++t)if(code[t] != 0){tag = false;break;}

				if(tag)

				{

					ans = max(ans,h[cur].f[k] + map[i][j]);

				}

			}

			if(left == 2 && up == 1)

			{

				code[j - 1] = 0;code[j] = 0;

				shift(code,code_,flag);

				h[cur ^ 1].add(encode(code_,m),h[cur].f[k] + map[i][j]);

			}

		}

	}

	return;

}

void solve()

{

	int cur = 0;

	h[cur].init();

	h[cur].add(0,0);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			h[cur ^ 1].init();

			dp(i,j,cur);

			cur ^= 1;

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)scanf("%d",&map[i][j]);

	solve();

	cout << ans << endl;

	return 0;

}