插头DP
题意：给出一个最多9*9的格盘描述，其中有两个2和两个3，求将两个2和3分别用不相交的线段相连所需的最短线长。线不能交叉且仅能经过空格。
明确是插头DP后，首先要考虑如何表示状态。这题特殊之处在于线段有两条，且需要和指定的端点相连。那么，最关键的是确定如何表达有效的终状态。
考虑以下解方案：用0表示空插头，2和3分别有相应插头。那么这里每个位置需要2bit，总共是2*10=20bit。再用最低的4个bit分别表示4个端点是否有连接，由此便能用一个int来表示轮廓线状态u。判断终状态时，直接用u==15即可。其正确性在于，题目所求的是最短线长，那么若4个端点已连，且当前没有空线头，则端点间必定已存在连线。同时也可能存在不与任何端点相连的线环，但线环仅仅是增加了总线长，不影响正确性。
实现方面，由于状态数为1<<24，若直接存下各个状态的最短线长，只能用char数组，由于题目数据范围不大，这是可行的。但一开始还是用了int数组和hash处理（u%10007)。按理说直接访问状态应该要比hash快，但事实上后者比前者要快两倍多（500ms VS 1600MS）。猜测是由于hash过后状态值较为接近，内存访问要更为集中。 虽然再加一些状态剪枝应该可以更快……但当前的代码长度竟已超过了5K，实在是不太明白那些2K左右跑出300ms的代码是怎么写的…… =(
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define M 1<<24 #define MS 1<<20 int n,m,ans; int x2s,y2s,x2e,y2e,x3s,y3s,x3e,y3e; int mem3[MS],mem4[MS]; int *st1,*st2,s1l,s2l; int b[9][9]; char mem1[M],mem2[M],*u1,*u2,ms[M],msij; int chk(int i,int j) { return i==n||j==m||b[i][j]==1; } bool chs(int i,int j,int &u,int v) { if(b[i][j]==v) { if(i==x2s&&j==y2s&&!(u&8)) { u|=8; return 1; } if(i==x2e&&j==y2e&&!(u&4)) { u|=4; return 1; } if(i==x3s&&j==y3s&&!(u&2)) { u|=2; return 1; } if(i==x3e&&j==y3e&&!(u&1)) { u|=1; return 1; } } return 0; } void adde(int u,int ud) { if(u==15) { ans=min(ans,ud); return; } else if(ud>=ans) return; if(ms[u]!=msij) { ms[u]=msij; u2[u]=ud; st2[s2l++]=u; } else u2[u]=min(u2[u],(char)ud); } void init() { int i,j,k,l; ans=0x7fffffff; x2s=y2s=x2e=y2e=x3s=y3s=x3e=y3e=-1; u1=mem1,u2=mem2; st1=mem3,st2=mem4,s1l=s2l=0; memset(ms,-1,sizeof ms); for(i=0;i<n;i++) { for(j=0;j<m;j++) { scanf("%d",&b[i][j]); if(b[i][j]==2) { if(x2s==-1) x2s=i,y2s=j; else if(x2e==-1) x2e=i,y2e=j; else ans=-1; } else if(b[i][j]==3) { if(x3s==-1) x3s=i,y3s=j; else if(x3e==-1) x3e=i,y3e=j; else ans=-1; } } } } int gt(int u,int l) { return (u>>(4+2*(m-l)))&3; } void st(int &u,int l,int v) { u&=~(3<<(4+2*(m-l))); u|=v<<(4+2*(m-l)); } void solve() { if(ans==-1) { puts("0"); return; } int i,j,k,l; int v1,v2,u,uu,ud; u1[0]=0; st1[s1l++]=0; for(i=0;i<n;i++) { for(j=0;j<m;j++) { msij=i*m+j; if(b[i][j]==1) continue; k=chk(i+1,j)*2+chk(i,j+1); while(s1l) { u=st1[--s1l]; ud=u1[u]; v1=gt(u,m); v2=gt(u,j); if(!v1&&!v2) { if(b[i][j]==0) { adde(u,ud); if(k==0) { uu=u; st(uu,j,2); st(uu,m,2); adde(uu,ud+1); uu=u; st(uu,j,3); st(uu,m,3); adde(uu,ud+1); } } else if(b[i][j]>1) { uu=u; if((k==0||k==1)&&chs(i,j,uu,b[i][j])) { st(uu,j,b[i][j]); st(uu,m,0); adde(uu,ud); } uu=u; if((k==0||k==2)&&chs(i,j,uu,b[i][j])) { st(uu,j,0); st(uu,m,b[i][j]); adde(uu,ud); } } } else if(!v1||!v2) { if(b[i][j]>1) { uu=u; if(chs(i,j,uu,v1+v2)) { st(uu,j,0); st(uu,m,0); adde(uu,ud); } } else if(b[i][j]==0) { if(k==0||k==1) { uu=u; st(uu,j,v1+v2); st(uu,m,0); adde(uu,ud+1); } if(k==0||k==2) { uu=u; st(uu,j,0); st(uu,m,v1+v2); adde(uu,ud+1); } } } else if(v1==v2) { if(b[i][j]==0) { uu=u; st(uu,j,0); st(uu,m,0); adde(uu,ud+1); } } } swap(u1,u2); swap(st1,st2); s1l=s2l; s2l=0; } } printf("%d\n",ans==0x7fffffff?0:ans+2); } int main() { while(~scanf("%d%d",&n,&m)&&n) { init(); solve(); } return 0; } |