fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. using namespace std;
  5. const int N = 503;
  6. int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1};
  7. bool vis[N][N][4];
  8. char grid[N][N];
  9. int dp[10][10][N][N], n, w, h;
  10. int tot = 0, l, r, id[N*N];
  11. pair<int,int> q1[N*N], q2[N*N], to[N][N][4], tt;
  12. pair<int,int> dfs(int x, int y, int d) { //recursion to find where (x,y) goes after 1 push
  13. 	if(vis[x][y][d]) return to[x][y][d];
  14. 	vis[x][y][d] = true;
  15. 	if(grid[x][y] == 'A') (++d) &= 3;
  16. 	if(grid[x][y] == 'C') (--d) &= 3;
  17. 	if(grid[x+dx[d]][y+dy[d]] == 'x')
  18. 		return {x,y};
  19. 	else
  20. 		return to[x+dx[d]][y+dy[d]][d] = dfs(x+dx[d],y+dy[d],d);
  21. }
  22. template <typename T> void check_min(T &a, T b) {if (b < a) a = b;}
  23. template <typename T> void check_max(T &a, T b) {if (b > a) a = b;}
  24. int c[N*N*20];
  25. void BFS(){
  26. 	int mx = 0,num;
  27. 	for(int i = 1; i <= tot; ++i){
  28.         if((num = dp[l][r][q1[i].x][q1[i].y]) != 1010580540){
  29.             mx = max(mx, num);
  30.         }
  31. 	}
  32. 	memset(c, 0, sizeof(int)*(mx + 2));
  33. 	for (int i = 1; i <= tot; ++i) {
  34. 		num = dp[l][r][q1[i].x][q1[i].y];
  35. 		if(num != 1010580540) ++c[num];
  36. 		else ++c[mx + 1];
  37. 	}
  38. 	for(int i = 1; i <= mx+1; ++i) c[i] += c[i - 1];
  39. 	for (int i = tot; i >= 1; --i) {
  40. 		num = dp[l][r][q1[i].x][q1[i].y];
  41. 		if (num == 1010580540) num = mx + 1;
  42. 		id[c[num]--] = i; //what is id?
  43. 	}
  44. 	int head = 1, tail = 0, tmp = 1, x, y, x2, y2;
  45. 	while(head <= tail || tmp <= tot){
  46. 		x = q2[head].x; y = q2[head].y;
  47. 		x2 = q1[id[tmp]].x; y2 = q1[id[tmp]].y;
  48. 		if (head <= tail && tmp <= tot && dp[l][r][x][y] < dp[l][r][x2][y2] || tmp > tot) ++head;
  49. 		else ++tmp, x = x2, y = y2;
  50. 		for (int d = 0; d < 4; ++d) {
  51. 			tt = to[x][y][d];
  52. 			if(tt.x == 0) continue;
  53. 			if(dp[l][r][tt.x][tt.y] > dp[l][r][x][y] + 1) { //we update this when the other one is smaller, because there is a second way to get it
  54. 				dp[l][r][tt.x][tt.y] = dp[l][r][x][y] + 1;
  55. 				q2[++tail] = tt;
  56. 			}
  57. 		}
  58. 	}
  59. }
  60.  
  61. int main() {
  62. 	cin >> n >> w >> h;
  63. 	memset(dp, 60, sizeof(dp));
  64. 	for(int i = 1; i <= h; ++i) cin >> grid[i]+1;
  65. 	for(int i = 1; i <= h; ++i) grid[i][0] = grid[i][w + 1] = 'x';
  66. 	for(int i = 1; i <= w; ++i) grid[0][i] = grid[h + 1][i] = 'x';
  67. 	for(int i = 1 ; i <= h; ++i)
  68. 		for(int j = 1; j <= w; ++j)
  69. 			if(grid[i][j] != 'x')
  70. 				for (int dt = 0; dt < 4; ++dt)
  71. 					to[i][j][dt] = dfs(i, j, dt);
  72.  
  73. 	for (int i = 1; i <= h; ++i)
  74. 		for (int j = 1; j <= w; ++j) q1[++tot] = make_pair(i, j);
  75.  
  76. 	bool flag;
  77. 	for(int i = n; i >= 1; --i){
  78. 		flag = false;
  79. 		for(int ii = 1; ii <= h; ++ii){
  80. 			for(int jj = 1; jj <= w; ++jj)
  81. 				if(grid[ii][jj] == '0' + i){
  82. 					dp[i][i][ii][jj] = 0;
  83. 					flag = true;
  84. 					break;
  85. 				}
  86. 			if(flag) break;
  87. 		}
  88. 		l = r = i; BFS();
  89. 		for(int j = i + 1; j <= n; ++j){
  90. 			for(int k = i; k < j; ++k)
  91. 				for(int ii = 1; ii <= h; ++ii)
  92. 					for(int jj = 1; jj <= w; ++jj)
  93. 						dp[i][j][ii][jj] = min(dp[i][j][ii][jj], dp[i][k][ii][jj]+dp[k + 1][j][ii][jj]);
  94. 			l = i; r = j; BFS();
  95. 		}
  96. 	}
  97.  
  98. 	int ans = 0x7fffffff;
  99. 	for (int i = 1; i <= h; ++i)
  100. 		for (int j = 1; j <= w; ++j)
  101. 			ans = min(ans, dp[1][n][i][j]);
  102. 	cout << (ans == 1010580540 ? -1 : ans) << "\n";
  103. 	return 0;
  104. }
Success #stdin #stdout 0.02s 104428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2147483647
https://ideone.com/wvhTbx
language:
C++14 (gcc 8.3)
created:
7 days 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!