[APIO2013]机器人

• 题意：P3638
• 思路:n<=9很容易想到斯坦纳树，然后就dp[i][l][r]表示合并到i号二维点，已合并区间[l,r]的最小步数。
  然后转移也和原来一样。注意这里spfa或dj会超，注意到边权为1，但是有多个源点，所以两个队列，一个存储初始，另一个存储更新，然后如果一个点进入过队列2或者入过且出过队，然后就不会再入队，这样复杂度也是O(n)。
  ps.卡常技巧
• 代码：

#include
using namespace std;
const int N=505;
const int M=N*N*4;
const int K=9;
char s[N][N];
int dp[N][N][4];
int up,p[N],inf=0x3f3f3f3f,f[K][K][N*N],nxt[M],head[N*N],to[M],ecnt,cc,n,w,h,dir[5][2]={{-1,0},{0,1},{1,0},{0,-1}};	//???? 
int Id(int x,int y) {return (x-1)*h+y;}
void add_edge(int u,int v) {if(u==v)return;nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
void DP(int x,int y,int d) {
	if(dp[x][y][d]!=-1)return;dp[x][y][d]=0;
	if(s[x][y]=='x'||x<1||y<1||x>w||y>h) {dp[x][y][d]=Id(x-dir[d][0],y-dir[d][1]);return;}
//	if(x==5&&y==7&&!d) printf("!\n");
	if(s[x][y]=='C') {DP(x+dir[(d+1)%4][0],y+dir[(d+1)%4][1],(d+1)%4);dp[x][y][d]=dp[x+dir[(d+1)%4][0]][y+dir[(d+1)%4][1]][(d+1)%4];return;}
	else if(s[x][y]=='A') {DP(x+dir[(d+3)%4][0],y+dir[(d+3)%4][1],(d+3)%4);dp[x][y][d]=dp[x+dir[(d+3)%4][0]][y+dir[(d+3)%4][1]][(d+3)%4];return;}
	int u=x+dir[d][0],v=y+dir[d][1];
	DP(u,v,d);dp[x][y][d]=dp[u][v][d];
}
bool in_s[N*N],_kk[N*N];
int h1,t1,h2,t2,Q1[N*N],Q2[N*N];
vectorV[M];
struct node {int p,w;}tmp[N*N];
bool cmp(node u,node v) {return u.wup)continue;
		tmp[++cc]=(node){i,f[x][y][i]};
//		V[f[i][x][y]].push_back(i);
		mx=max(mx,f[x][y][i]);
	}
	if(cc*10>mx) {
		for(int i=1;i<=cc;i++) V[tmp[i].w].push_back(tmp[i].p);
		for(int i=0;i<=mx;i++)
			if(V[i].size()) {
				for(int j=0;jw) {
				f[x][y][v]=w;
				Q2[++t2]=v;in_s[v]=1;
			}
		}
	}
	for(int i=1;i<=h*w;i++) in_s[i]=_kk[i]=0;
}
void solve() {
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++) {
		f[i-1][i-1][p[i]]=0;
	}
	for(int len=1;len<=n;len++) {
		for(int i=0,tt=n-len;i<=tt;i++) {
			int j=i+len-1;
			for(int u=1;u<=up;u++) {
				for(int mid=i;mid='1'&&s[i][j]<='9') p[s[i][j]-'0']=Id(i,j);
		for(int d=0;d<4;d++) {
			DP(i,j,d);
			if(dp[i][j][d])add_edge(Id(i,j),dp[i][j][d]);
//			printf("(%d,%d) [->%d]: (%d,%d)\n",i,j,d,ix[dp[i][j][d]],iy[dp[i][j][d]]);
		}
	}
//	for(int i=1;i<=n;i++) printf("%d ",p[i]);
	solve();
	return 0;
}
//2 6 2
//C1CA2A
//CCCAAA