在一个市上，存在着很多的空地和住宅。现在，城市中新开了一个水果店，为了向城市居民问好，水果店决定派两个送货员向每一处住宅送一箱水果。由于一箱水果的重量很大，所以送货员每次只能携带一箱水果。 你可以把这个城市看成一个N行M列的棋盘，每个格子要么是空地，要么是住宅，要么是水果店。如果这个格子是一个空地，那就用0..9来表示这个空地的高度；如果是住宅，那么就用$来表示，如果是水果店，那么就用X来表示。从一个格子进入另一个格子，当且仅当两个格子相邻，也就是说共享一条边。 如果两个格子中有一个是住宅或水果店，那么需要花费2分钟的时间。 如果两个格子都是空地，那么就按高度来讨论时间。如果两个空地的高度相同，则花费1分钟的时间；如果两者的高度差1，则花费3分钟的时间；如果两者的高度超过1，那么不能互相进入。 现在，水果店的老板想知道，如果让整个城市的住宅都收到自己的水果，最短需要多少时间呢？如果永远无法送到，请输出-1。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,f[114][514],dx[4]={0,1,0,(~1)|1},dy[4]={1,0,(~1)|1,0},d[21],num=0,s1=0,s2=0,ans=(~1)|1,mx1=(~1)|1,mx2=(~1)|1,tmp2;
char g[114][514];
void dfs(int ux,int uy){
	for(register int i=0;i<4;i++){
		int x=ux+dx[i],y=uy+dy[i];
		int tmp=f[x][y];
		if(g[x][y]=='X')continue;
		if(x<1|x>n|y<1|y>m)continue;
		if(g[x][y]=='$'||g[ux][uy]=='X'||g[ux][uy]=='$'){
			if((!(f[x][y]^((~1)|1)))||f[x][y]>f[ux][uy]+(1<<1))f[x][y]=f[ux][uy]+(1<<1); 
		}
		else if(isalnum(g[x][y])&isalnum(g[ux][uy])){
			int p=abs(g[x][y]-g[ux][uy]);
			if(p<2){
				if((!(f[x][y]^((~1)|1)))||f[x][y]>f[ux][uy]+((p<<1)|1))f[x][y]=f[ux][uy]+((p<<1)|1); 
			}
		}
		if(f[x][y]^tmp)dfs(x,y);
	}
}
void dfs2(int u){
	if(u>num){
		int t1=s1,t2=s2;
		if((mx1^((~1)|1)))t1-=mx1;
		if((mx2^((~1)|1)))t2-=mx2;
		if(!(ans^((~1)|1)))ans=max(t1,t2);
		else ans=min(ans,max(t1,t2));
		return;
	}
	tmp2=mx1,s1+=(d[u]<<1);
	if(d[u]>mx1||(!(mx1^((~1)|1))))mx1=d[u];
	dfs2(u+1);
	s1-=(d[u]<<1),mx1=tmp2;
	tmp2=mx2,s2+=(d[u]<<1);
	if(d[u]>mx2||(!(mx2^((~1)|1))))mx2=d[u];
	dfs2(u+1);
	s2-=(d[u]<<1),mx1=tmp2;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(register int i=1;i<=n;i++){
		cin>>g[i]+1;
		for(register int j=1;j<=m;j++){
			if(g[i][j]=='X')sx=i,sy=j;
		}
	}
	memset(f,((~1)|1),sizeof(f));
	f[sx][sy]&=0;
	dfs(sx,sy);
	for(register int i=1;i<=n;i++)
		for(register int j=1;j<=m;j++){
			if(g[i][j]=='$'){
				if(f[i][j]==-1){
					cout<<-1;
					return 65536;
				}
				d[++num]=f[i][j];
			}
		}
	dfs2(1);
	cout<<ans;
}

$60$ 分求调