#include #include #include #include #include #include using namespace std; //#define PRINTF(args...) printf(args) #define PRINTF(args...) #define FOR(i,a,b) for(int i=(a); i<(int)(b); ++i) #define FORD(i,a,b) for(int i=(a)-1; i>=(int)(b); --i) #define FOREACH(i,C) for(__typeof(C.begin()) i=C.begin(); i!=C.end(); ++i) int n; char tab[42][42]; int dist[40][40][40][40]; int dp[1<<4]; int distP[40][40][4]; bool vis[1<<4]; const int INF = 1000000; int count(int x0, int y0, int x1, int y1) { if(x0>x1) { swap(x0,x1); swap(y0,y1); } int res = x1-x0; int k = y1-y0; if(x0res) res = k; } else { if(x1+k(n-x0-1)) res += k-(n-x0-1); } } else { if(k>0) res += k; else if(-k>res) res = -k; } res--; return max(0,res); } int bitCount(int k) { int res = 0; while(k) { res += k%2; k /= 2; } return res; } int go(int mask) { int &res = dp[mask]; if(vis[mask]) return res; vis[mask] = true; if(bitCount(mask)<=1) return res = 0; //printf("maskIn=%d res=%d\n",mask,res); FOR(i,0,(1<<4)) FOR(j,0,(1<<4)) if((i&mask)==i && (j&mask)==j && i0 && bitCount(i)>=2 && bitCount(j)>=2 && (i|j)==mask) res 0) break; } else if(c=='.' || (c<='D' && c>='A')) tab[i][j++] = c; PRINTF("%d %c\n",j,c); } tab[i][j++] = 0; //printf("%d %s\n",i,tab[i]); } FOR(i,0,(2*n-1)) { int bI = 2*n-1-abs(n-(i+1)); FOR(j,0,bI) FOR(a,0,(2*n-1)) { int bA = 2*n-1-abs(n-(a+1)); FOR(b,0,bA) dist[i][j][a][b] = count(i,j,a,b); } } FOR(i,0,(1<<4)) dp[i] = INF; FOR(a,0,(2*n-1)) { int bA = 2*n-1-abs(n-(a+1)); FOR(b,0,bA) FOR(i,0,4) distP[a][b][i] = INF; } FOR(i,0,(2*n-1)) { int bI = 2*n-1-abs(n-(i+1)); FOR(j,0,bI) FOR(a,0,(2*n-1)) { int bA = 2*n-1-abs(n-(a+1)); FOR(b,0,bA) { int nI = tab[i][j]-'A', nA=tab[a][b]-'A'; if(nI>=0 && nI<=3 && nA>=0 && nA<=3) { dp[(1<=0 && nI<=3) distP[a][b][nI] =0 && nA<=3) distP[i][j][nA]