fork(3) download
copy 
  1. #include<algorithm>
  2. #include<vector>
  3. #include<iostream>
  4. #include<string>
  5. #include<cstring>
  6. #include<cstdio>
  7. #include<queue>
  8.  
  9. #define fr first
  10. #define sc second
  11. #define mp make_pair
  12. #define pb push_back
  13. #define REP(i,m) for(int i=0;i<(int)m;++i)
  14. #define REPN(i,m,in) for(int i=in;i<(int)m;++i)
  15. #define ALL(t) (t).begin(),(t).end()
  16. #define dump(x) cerr<<#x<<" = "<<x<<endl
  17. #define prl cerr<<"LINE "<<__LINE__<<" is called"<<endl
  18.  
  19. using namespace std;
  20. template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' '; cerr<<endl ; }
  21.  
  22. typedef pair<int,int> pi;
  23. typedef long long int lint;
  24. const int INF=510000000;
  25.  
  26. char buf[505][505];
  27. int dp[50][505][505];
  28.  
  29. pi g[505][505][4];
  30.  
  31. bool vis[505][505][4];
  32.  
  33. int n,w,h;
  34. int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
  35. pi rec(int y,int x,int d){
  36.     pi& res=g[y][x][d];
  37. 	if(res.fr!=-1) return res;
  38. 	if(vis[y][x][d]) return res=mp(-2,-2);
  39. 	vis[y][x][d]=1;
  40.  
  41. 	if(buf[y][x]=='A') d=(d+1)%4;
  42. 	if(buf[y][x]=='C') d=(d+3)%4;
  43.  
  44. 	int px=x+dx[d],py=y+dy[d];
  45. 	if(px<0 || py<0 || px>=w || py>=h || buf[py][px]=='x'){
  46. 		return res=mp(y,x);
  47. 	}
  48. 	return res=rec(py,px,d);
  49. }
  50.  
  51. pi pos[10];
  52. int hash[10][10];
  53.  
  54. void prep(int sy,int sx,int id){
  55. 	queue<pi> q;
  56. 	dp[hash[id][id+1]][sy][sx]=0;
  57. 	q.push(mp(sy,sx));
  58.  
  59. 	while(!q.empty()){
  60. 		pi cur=q.front();q.pop();
  61.  
  62. 		REP(d,4){
  63. 			pi to=g[cur.fr][cur.sc][d];
  64.  
  65. 			if(to.fr==-2) continue;
  66.  
  67. 			if(dp[hash[id][id+1]][to.fr][to.sc]!=-1) continue;
  68.  
  69. 			dp[hash[id][id+1]][to.fr][to.sc]=dp[hash[id][id+1]][cur.fr][cur.sc]+1;
  70.  
  71. 			q.push(to);
  72. 		}
  73. 	}
  74.  
  75. 	REP(i,h) REP(j,w) if(dp[hash[id][id+1]][i][j]==-1) dp[hash[id][id+1]][i][j]=INF;
  76. }
  77.  
  78. vector<pi> posByCost[500*501*10];
  79. vector<int> used;
  80.  
  81. int main(){
  82. 	int cntt=0;
  83. 	REP(i,9) REPN(j,10,i+1) hash[i][j]=cntt++;
  84. 	scanf("%d%d%d",&n,&w,&h);
  85.  
  86. 	REP(i,h) scanf("%s",buf[i]);
  87. 	REP(i,h) REP(j,w){
  88. 		if(buf[i][j]>='1' && buf[i][j]<='9'){
  89. 			pos[buf[i][j]-'1']=mp(i,j);
  90. 		}
  91. 	}
  92. 	memset(g,-1,sizeof(g));
  93. 	REP(i,h) REP(j,w) REP(d,4) rec(i,j,d);
  94.  
  95. 	memset(dp,-1,sizeof(dp));
  96. 	REP(i,n){
  97. 		prep(pos[i].fr,pos[i].sc,i);
  98. 	}
  99.  
  100.  
  101. 	queue<pi> q;
  102.  
  103. 	for(int len=2;len<=n;++len) REP(i,n-len+1){
  104. 		int j=i+len;
  105.  
  106. 		pair<int,pi> mini;mini.fr=INF;
  107.  
  108. 		REP(y,h) REP(x,w){
  109. 			dp[hash[i][j]][y][x]=INF;
  110. 			REP(k,len-1){
  111. 				int div=i+k+1;
  112. 				dp[hash[i][j]][y][x]=min(dp[hash[i][j]][y][x],dp[hash[i][div]][y][x]+dp[hash[div][j]][y][x]);
  113. 			}
  114. 			if(dp[hash[i][j]][y][x]!=INF){
  115. 				used.pb(dp[hash[i][j]][y][x]);
  116. 				posByCost[dp[hash[i][j]][y][x]].pb(mp(y,x));
  117. 				mini=min(mini,mp(dp[hash[i][j]][y][x],mp(y,x)));
  118. 			}
  119. 		}
  120. 		if(mini.fr==INF) continue;
  121. 		REP(k,posByCost[mini.fr].size()) q.push(posByCost[mini.fr][k]);
  122. 		posByCost[mini.fr].clear();
  123.  
  124.  
  125. 		while(!q.empty()){
  126.  
  127. 			pi p=q.front();q.pop();
  128. 			int c=dp[hash[i][j]][p.fr][p.sc];
  129. 			if(!posByCost[c+1].empty()){
  130. 				REP(k,posByCost[c+1].size()){
  131. 					pi p2=posByCost[c+1][k];
  132. 					if(dp[hash[i][j]][p2.fr][p2.sc]<c+1) continue;
  133. 					q.push(p2);
  134. 				}
  135. 				posByCost[c+1].clear();
  136. 			}
  137. 			REP(d,4){
  138. 				pi nxt=g[p.fr][p.sc][d];
  139. 				if(nxt.fr==-2 || dp[hash[i][j]][nxt.fr][nxt.sc]<=c+1) continue;
  140. 				dp[hash[i][j]][nxt.fr][nxt.sc]=c+1;
  141. 				q.push(nxt);
  142. 			}
  143.  
  144. 		}
  145. 		REP(k,used.size()) posByCost[used[k]].clear();
  146. 		used.clear();
  147.  
  148.  
  149. 	}
  150.  
  151. 	int res=INF;
  152.  
  153. 	REP(i,h) REP(j,w) res=min(res,dp[hash[0][n]][i][j]);
  154.  
  155. 	if(res==INF) res=-1;
  156.  
  157. 	printf("%d\n",res);
  158.  
  159.  
  160.  
  161. 	return 0;
  162. }
  163.  
  164.  
Success #stdin #stdout 0.08s 91392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/96vMcn
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!