自动搬运

查看原文

来自洛谷，原作者为

	stntn 假如再也见不到你，祝你早安，午安，晚安。

搬运于2025-08-24 21:47:38，当前版本为作者最后更新于2023-03-21 20:30:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

插头 DP。

为什么一篇题解都没有害得我调了一天。

本题数据范围 $n,m \le 9,k \le 10$。

记录当前插头状态的最短线路长度和方案数。插头分 $k$ 种，这里可以不使用括号表示法，因为如果出现一些不合法的路径（比如空地上无电源出现回路）一定不优会被舍去。

然后就是分类讨论：

令 $fr$ 为当前左插头，$fd$ 为当前上插头。

1. 当前格为障碍物：

   • 当前格非电源且 $fr=fd=0$ 转移到无上下插头。

2. 当前格为电源：

   • 当前有两个相同插头不合法。

   • 当前的插头不属于该电源不合法。

   • 如果该电源的仍需要向外连接 $>2$ 条线路不合法。

   • 枚举出路转移。

3. 当前格为空地：

   • $fr=fd=0$ ：转移到无插头或新建从右至下的某种电线。

   • $(fr=0 \land fd>0)\lor(fr>0 \land fd=0)$：延续插头至下或右。

   • $fr>0 \land fd>0 \land fr \ne fd$：延续至“左-下，上-右”插头。

   • $fr=fd \land fr>0$ 合并插头，转移到转移到无插头或新建从右至下的某种电线。

注意事项：

1. 若某种电线起点终点为同一格子则无解。

2. 积极提前判断不合法状态优化状态数量。

3. 多测清空。

CODE

#include<bits/stdc++.h>
#define N 10
#define M 100010
#define S 3000010
#define LL long long
#define DB double
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define mod 25619849
#define INF 0x3f3f3f3f
#define pir pair<int,int>
#define mp(i,j) make_pair(i,j)
#define fi first
#define se second
#define w(i,j) (1ll*((1ll*i)<<(j)))
#define e(i,j) (1ll*(((1ll*i)>>(j))&15))
using namespace std;
template <typename T> inline void read(T &a)
{
	a=0;T w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch^48);ch=getchar();}
	a*=w;
}
template <typename T,typename ...Args> inline
void read(T &x,Args &...args){read(x);read(args...);}
int n,m,q,maap[N][N],num[N+1],ncc;
bool suc;
const LL lim=(1ll<<40)-1;
bool cur,hav[N][N][11];
vector<int> node[N][N];
struct HASH_TABLE
{
	#define Mod 500009
	struct NODE{int pre,id;}a[S];
	int head[500010],cc,pcc;//插头4*9=36位？ 
	LL state[S],f[S];int g[S];
	inline void init(){pcc=0;memset(head,0,sizeof(head));}
	inline void insert(LL sta,LL val,int len)
	{
		sta&=lim;int key=1ll*sta%Mod;
		for(int cur=head[key];cur;cur=a[cur].pre) if(state[a[cur].id]==sta)
		{
			int id=a[cur].id;
			if(g[id]>len){g[id]=len;f[id]=val;return;}
			else if(g[id]==len){(f[id]+=val)%=mod;return;}
			else return;
		}
		a[++pcc]={head[key],++cc};head[key]=pcc;state[cc]=sta;f[cc]=val;g[cc]=len;
	}
	#undef Mod
}hs[2];
inline void Main()
{
	memset(hav,0,sizeof(hav));
	swap(n,m);cur=0;suc=1;
	rep(i,1,n) rep(j,1,m) read(maap[i][j]),node[i][j].clear();
	rep(i,1,q)
	{
		int x,y,_x,_y;read(x,y,_x,_y);
		x++;y++;_x++;_y++;
		if(x==_x&&y==_y){suc=0;}
		node[ x][ y].push_back(i);
		node[_x][_y].push_back(i);
		hav[x][y][i]=hav[_x][_y][i]=1;
		if(node[ x][ y].size()>4){suc=0;}
		if(node[_x][_y].size()>4){suc=0;}
	}
	rep(i,1,n) rep(j,1,m) if(!node[i][j].size()) rep(k,1,q) hav[i][j][k]=1;
	if(!suc){printf("-1 0\n");return;}
	hs[0].init();hs[0].cc=0;
	hs[1].init();hs[1].cc=0;
	hs[cur].init();hs[cur].cc=0;hs[cur].insert(0,1,0);
	rep(i,1,n)
	{
		rep(j,1,hs[cur].cc) (hs[cur].state[j]<<=4)&=lim;
		rep(j,1,m)
		{
			hs[cur].init();cur^=1;hs[cur].cc=0;
			rep(k,1,hs[cur^1].cc)
			{
				LL sta=hs[cur^1].state[k]&lim,val=hs[cur^1].f[k];int len=hs[cur^1].g[k];
				int fr=e(sta,(j-1)*4),fd=e(sta,j*4);
				LL base=sta^w(fr,(j-1)*4)^w(fd,j*4);
				if(maap[i][j]==1)
				{
					if(node[i][j].size()) continue;
					if(!fd&&!fr) hs[cur].insert(base,val,len);
				}
				else if(!node[i][j].size())
				{
					if(!fr&&!fd)
					{
						hs[cur].insert(base,val,len);
						if(j<m&&!maap[i][j+1]&&i<n&&!maap[i+1][j]) rep(typ,1,q) if(hav[i][j+1][typ]&&hav[i+1][j][typ]) hs[cur].insert(base|w(typ,(j-1)*4)|w(typ,j*4),val,len+2);
					}
					else if((fr&&!fd)||(!fr&&fd))
					{
						if(i<n&&!maap[i+1][j]&&hav[i+1][j][fr|fd]) hs[cur].insert(base|w(fr|fd,(j-1)*4),val,len+1);
						if(j<m&&!maap[i][j+1]&&hav[i][j+1][fr|fd]) hs[cur].insert(base|w(fr|fd,j*4),val,len+1);
					}
					else if(fr&&fd)
					{
						if(fd==fr)
						{
							hs[cur].insert(base,val,len);
							if(j<m&&!maap[i][j+1]&&i<n&&!maap[i+1][j]) rep(typ,1,q) if(typ^fr&&hav[i][j+1][typ]&&hav[i+1][j][typ]) hs[cur].insert(base|w(typ,(j-1)*4)|w(typ,j*4),val,len+2);
						}
						else if(j<m&&!maap[i][j+1]&&i<n&&!maap[i+1][j]&&hav[i][j+1][fd]&&hav[i+1][j][fr]) hs[cur].insert(base|w(fr,(j-1)*4)|w(fd,j*4),val,len+2);
					}
					else assert(0);
				}
				else
				{
					if(fr==fd&&fr) continue;
					bool afr=0,afd=0;ncc=0;
					for(int x:node[i][j]){if(x==fr) afr=1;if(x==fd) afd=1;}
					if(fr&&!afr) continue;
					if(fd&&!afd) continue;
					for(int x:node[i][j]) if(x^fr&&x^fd) num[++ncc]=x;
					if(ncc==0)
					{
						hs[cur].insert(base,val,len);
					}
					else if(ncc==1)
					{
						int x=num[1];
						if(j<m&&!maap[i][j+1]&&hav[i][j+1][x]) hs[cur].insert(base|w(x,j    *4),val,len+1);
						if(i<n&&!maap[i+1][j]&&hav[i+1][j][x]) hs[cur].insert(base|w(x,(j-1)*4),val,len+1);
					}
					else if(ncc==2)
					{
						if(j>=m||i>=n||maap[i][j+1]||maap[i+1][j]) continue;
						if(hav[i+1][j][num[1]]&&hav[i][j+1][num[2]]) hs[cur].insert(base|w(num[1],(j-1)*4)|w(num[2],j*4),val,len+2);
						if(hav[i+1][j][num[2]]&&hav[i][j+1][num[1]]) hs[cur].insert(base|w(num[2],(j-1)*4)|w(num[1],j*4),val,len+2);
					}
				}
			}
		}
	}
	rep(i,1,hs[cur].cc) if(!hs[cur].state[i]) return printf("%d %lld\n",hs[cur].g[i],hs[cur].f[i]),void();
	printf("-1 0\n");
}
signed main()
{
	while(1)
	{
		read(n,m,q);
		if(!(n+m+q)) break;
		Main();
	}
	return 0;
}