插头DP
做完Formula 1以后这就是傻逼题了……直接将“数路径方案数”改为“计算路径长度取最小值”即可，没多大难度
都不用判当前格子是否能够到达的……不过！外边的一圈“墙”还是要加的！不然会有冗余状态……会TLE（如果是有障碍物的题的话直接就WA了，@楼教主的Tonys Tour）
比较蛋疼的是地图的读入……不过好好思考一下还是可以写出来的= =（sigh……花了半小时）
调了一上午的原因？……
两个左插头的时候要向右找，遇到左插头计数器+1，遇到右插头计数器-1。
而两个右插头的时候向左找，过程刚好相反……但我写反了啊！！！仍旧是左+右-了……so sad……傻逼错误毁一生啊！
//HDU 1964
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
//#define debug
typedef unsigned long long u64;
typedef long long LL;
const int M=,INF=;
u64 mp[][][];
int n,m,k;
int tot[],bit[],hash[M],state[][M];
u64 dp[][M],ans; void init(){
F(i,,) F(j,,) F(k,,) mp[i][j][k]=INF;
CC(dp,);
tot[]=,k=,ans=INF;
state[][]=dp[][]=;
char ch;
char s[];
scanf("%d%d%*c",&n,&m);
gets(s);
F(i,,(n<<)-){
gets(s);//读一整行，含换行符
if (i&){
F(j,,m-<<)
if ((j&)==) mp[(i>>)+][j>>][]=s[j]-'';
}
else{
int temp=;
F(j,,m){
mp[i>>][j][]=s[temp]-'';
temp+=;
}
}
}
scanf("%s\n",s);
}
inline void hash_in(int s,u64 sum){
int p=s%M;
while(hash[p]){
if (state[k][hash[p]]==s){
dp[k][hash[p]]=min(dp[k][hash[p]],sum);
return;
}
p++;
if (p==M) p=;
}
hash[p]=++tot[k];
state[k][hash[p]]=s;
dp[k][hash[p]]=sum;
}
#define in hash_in(s,sum)
void work(){
F(i,,n){
F(j,,m){
k^=;
tot[k]=;
CC(hash,);
F(u,,tot[-k]){
int s=state[-k][u];
u64 sum=dp[-k][u];
int p=(s>>bit[j-])&,q=(s>>bit[j])&;
if (!p && !q){
s=s^(<<bit[j-])^(<<bit[j]<<);
hash_in(s,sum+mp[i][j][]+mp[i][j][]);
}else if(!p && q){
hash_in(s,sum+mp[i][j][]);
s=s^q*(<<bit[j-])^q*(<<bit[j]);
hash_in(s,sum+mp[i][j][]);
}else if(p && !q){
hash_in(s,sum+mp[i][j][]);
s=s^p*(<<bit[j-])^p*(<<bit[j]);
hash_in(s,sum+mp[i][j][]);
}else if(p+q==){
int nd=;
F(u,j+,m){
int w=(s>>bit[u])&;
if (w==) nd++;
if (w==) nd--;
if (!nd) {s-=(<<bit[u]); break;}
}
s=s^(<<bit[j])^(<<bit[j-]);hash_in(s,sum);
}else if(p+q==){
int nd=;
D(u,j-,){
int w=(s>>bit[u])&;
if (w==) nd++;
if (w==) nd--;
if (!nd) {s+=(<<bit[u]); break;}
}
s=s^(<<bit[j]<<)^(<<bit[j-]<<);hash_in(s,sum);
}else if(p== && q==){
if (i==n && j==m) ans=min(sum,ans);
}else if(p== && q==) s=s^(<<bit[j-]<<)^(<<bit[j]),in;
}
}
F(j,,tot[k]) state[k][j]<<=;
}
printf("%llu\n",ans);
}
int main(){
F(i,,) bit[i]=i<<;
int T;
scanf("%d",&T);
while(T--){
init();
work();
}
return ;
}